Белые мишки отправились на рыбалку. Они собираются сесть в лодку и доплыть от (sx, sy) до (ex, ey). Однако лодка поддается управлению только силы ветра. Каждую секунду ветер дует в одном из следующих направлений: на восток, на юг, на запад или на север. Предположим, что на данный момент лодка находится в (x, y).
- Если ветер дует на восток, то лодка поплывет на (x + 1, y).
- Если ветер дует на юг, то лодка поплывет на (x, y - 1).
- Если ветер дует на запад, то лодка поплывет на (x - 1, y).
- Если ветер дует на север, то лодка поплывет на (x, y + 1).
Мишки могут остановить лодку, бросив якорь. Тогда лодка остается на (x, y), независимо от того куда дует ветер. Зная направление ветра в следующие t секунд, определите самый ранний момент, когда они смогут приплыть к (ex, ey).
Выходные данные
Если можно доплыть до (ex, ey) в течение t секунд, выведите самое раннее время, когда мишкам это удастся. В противном случае выведите «-1» (без кавычек).
Примечание
В первом примере можно бросить якорь в секунды 1, 3 и двигаться в секунды 2, 4.
Во втором примере мишкам не удастся доплыть до пункта назначения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 0 0 1 1
SESNW
|
4
|
|
2
|
10 5 3 3 6
NENSWESNEE
|
-1
|