H. Quantum Realms
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
2 2
00
00
0 0 0 0
5 6 0 0
0 0 0 0
0 0 0 0
1 4
1 2
Output
10
Input
3 3
000
010
000
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
2 1
3 3
4 1
Output
11
Input
4 2
00
11
11
00
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1
2 2
Output
-1
Input
5 5
00000
01110
01010
10110
00000
0 9 7 9
8 5 9 9
1 8 5 3
6 9 6 2
3 2
2 4
4 3
1 1
2 4
Output
45