stringDiscover

Kỳ nghỉ hè sắp kết thúc và Victor đang chuẩn bị đi khám phá một khu rừng. Điểm khởi đầu là gốc tọa độ (0, 0), để miêu tả quá trình di chuyển ta sử dụng một trong bốn ký tự:

1. E là quá trình đi từ (x, y) đến (x + 1, y).
2. W là quá trình đi từ (x, y) đến (x - 1, y).
3. S là quá trình đi từ (x, y) đến (x, y - 1).
4. N là quá trình đi từ (x, y) đến (x, y + 1).

Từ bốn ký tự trên Victor đã tạo ra một chuỗi mô tả đoạn đường cần đi. Giờ đây vấn đề nan giải là phải ước lượng được thời gian hoàn thành chuyến đi để đặt lịch cho phù hợp. Trên đoạn đường hai chiều như nhau giữa hai điểm cách nhau 1 đơn vị, đối với lần đầu tiên đi qua Victor sẽ mất 3 giờ để tìm hiểu cảnh vật xung quanh, đối với các lần sau vì đã qua đoạn đường này trước đó nên Victor rút ngắn thời gian xuống 1 giờ để kịp tiến độ. Cho một chuỗi s, hãy tính toán thời gian Victor cần để hoàn thành việc khám phá khu rừng.

Ví dụ:

• Với s = "ENWSE" thì string_Discover = 13. Vì:
  • s[1] = 'E' ta đi từ (0, 0) đến (1, 0) mất 3h.
  • s[2] = 'N' ta đi từ (1, 0) đến (1, 1) mất 3h.
  • s[3] = 'W' ta đi từ (1, 1) đến (0, 1) mất 3h.
  • s[4] = 'S' ta đi từ (0, 1) đến (0, 0) mất 3h.
  • s[5] = 'E' ta đi từ (0, 0) đến (1, 0), đoạn đường này đã khám phá trước đó nên chỉ mất 1h.

Vậy mất tổng cộng 3 + 3 + 3 + 3 + 1 = 13h.

Đầu vào/Đầu ra:

• [Thời gian chạy] 1 giây với C++, 6 giây với Java và C#, 8 giây với Python, Go và Js.
• [Đầu vào] String s.
  5 ≤ n.length ≤ 100000.
• [Đầu ra] Integer.
  Thời gian Victor cần để hoàn thành chuyến đi.