← 返回题目列表

Codeforces · 298/B

B. 帆

中文机器翻译题面 查看原题

北极熊去钓鱼了。他们计划从 (sx, sy) 航行到 (ex, ey)。然而,船只能靠风航行。每一秒,风都会朝以下方向之一吹:东、南、西或北。假设船当前位于 (x, y)。

- 如果风向东吹,船将移动到 (x + 1, y)。
- 如果风向南吹,船将移动到 (x, y - 1)。
- 如果风向西吹,船将移动到 (x - 1, y)。
- 如果风向北吹,船将移动到 (x, y + 1)。

或者,他们可以用锚固定住船。在这种情况下,船停留在 (x, y)。给定 t 秒的风向,他们最早航行到 (ex, ey) 的时间是多少?

输入

第一行包含五个整数 t, sx, sy, ex, ey (1 ≤ t ≤ 105, - 109 ≤ sx, sy, ex, ey ≤ 109)。起始位置和结束位置将会不同。

第二行有t个字符,第i个字符是第i秒的风向。它将是四种可能性之一:“E”(东)、“S”(南)、“W”(西)和“N”(北)。

输出

如果他们可以在 t 秒内到达 (ex, ey),则打印他们可以到达的最早时间。否则,打印“-1”(不带引号)。

示例

输入 #1

5 0 0 1 1
SESNW

输出 #1

4

输入 #2

10 5 3 3 6
NENSWESNEE

输出 #2

-1

注意

在第一个示例中,它们可以停留在第 1、3 秒,并在第 2、4 秒移动。

在第二个示例中,他们无法航行到目的地。