E. Maze Ball
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
3 3 2 2 1 2 3
0 0 0
0 1 0
0 0 0
Output
3
Input
7 7 3 1 1 2 5
0 0 0 1 0 0 0
0 0 0 1 0 0 0
1 1 0 1 0 1 0
0 0 0 1 0 0 0
0 0 0 0 0 1 0
0 0 1 0 0 0 0
0 0 0 0 0 0 0
Output
4
Input
5 5 3 1 1 1 5
0 0 1 0 0
0 0 1 1 0
0 0 0 1 0
0 0 1 0 0
0 0 0 0 0
Output
3
Input
3 3 2 1 1 2 2
0 0 0
0 0 0
0 0 0
Output
-1