北极熊去钓鱼了。他们计划从 (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 秒移动。
在第二个示例中,他们无法航行到目的地。