Рабочее место участника

Чтобы добраться до источника живой воды, путешественник должен пройти через лабиринт. Не всегда существует путь к источнику, но путешественник может проходить сквозь стены, используя магию. К сожалению, путешественник может использовать магию только ограниченное количество раз, а до источника необходимо добраться как можно быстрее.

Лабиринт имеет форму квадрата, который состоит из `N`x`N` квадратных клеток, внутри которого вдоль сторон клеток могут быть расположены стены.

В каждый момент времени путешественник может находиться в одной и только в одной клетке лабиринта.

Одним ходом считается перемещение путешественника в соседнюю по горизонтали или по вертикали клетку. Путешественник может `K` раз проходить сквозь стену и не может выходить за пределы лабиринта.

Составьте программу, которая вычислит минимальное количество ходов, за которое путешественник может добраться до источника с координатами `(P,\ Q)`, начав путь в клетке с координатами `(1,\ 1)`.

Входной файл в первой строке содержит числа `N`, `K`, `P`, `Q` (`2\ ≤\ N\ ≤\ 200`, `0\ ≤\ K\ ≤\ 250`, `1\ ≤\ P,\ Q\ ≤\ N`). Следующие `N-1` строк содержат по `N` целых чисел – признаков наличия горизонтальных стен между клетками. Следующие `N` строк содержат `N-1` целых чисел  – признаков наличия вертикальных стен между клетками. 0 означает отсутствие стены, 1 – присутствие.

Единственная строка выходного файла должна содержать найденное минимальное количество ходов, или число `-1`, если путь найти не удалось.

3 1 2 3
0 0 0
0 1 0
1 0
1 0
0 0

3