Raptor

pamięć: 64MB

W związku ze zbliżającym się końcem świata Ziemię zaatakowały welociraptory (rodzaj niewielkich teropodów z rodziny dromeozaurów). To oczywiście wątek główny nadchodzącego hitu kinowego. W kluczowej scenie ucieczki główny bohater znajduje się w opustoszałym mieście, gdzie czyhają na niego welociraptory. Bohater potrzebuje jednej sekundy by przejść z jednego pola na sąsiednie (o wspólnym boku). Mając dany czas, jakiego potrzebują welociraptory na takie przejście oraz plan miasta z zaznaczonym początkowym położeniem każdego raptora, znajdź najkrótszą drogę, po której niezależnie od (nieznanych bohaterowi) zachowań raptorów będzie można bezpiecznie przejść do wskazanego miejsca.

Wejście

W pierwszej linii wejścia dana jest 5 liczb: liczba wierszy i kolumn mapy 5≤N,M≤2000, liczba sekund potrzebna raptorowi na przejście 2≤V≤10 i współrzędne punktu docelowego 1≤ex,ey≤2000. Punktem początkowym bohatera jest 1,1.
Następnie każda z N linii, każda po M znaków, opisuje mapę. W danym polu mapy # oznacza ścianę, na którą nikt nie może wejść, . oznacza puste pole, litery w oznaczają początkowe pozycje poszczególnych welociraptorów. W 80% testów na mapie jest dokładnie jeden raptor.

Wyjście

Wypisz jedną liczbę - długość (w sekundach) najkrótszej drogi z (1,1) do (ex,ey), na której (poruszając się stale o pole na sekundę) na pewno nie napotkamy raptora. Wypisz -1 jeżeli takiej drogi nie ma.

Przykład

Tu bohater musi przebiec dłuższą, dolną drogą, by uniknąć zjedzenia.

wejściewyjście
4 6  5  3 6
.###w#
......
.####.
......
9

Tu nawet biegnąc na około zostanie w ostatniej chwili pożarty.

wejściewyjście
4 6  5  2 6
.###w#
......
.####.
......
-1

A tu może czmychnąć tuż przed raptorem.

wejściewyjście
4 6  5  3 6
.##w##
......
.####.
......
7