Input:
4 4 4
1 2 1 1
1 1 1 1
1 1 1 1
1 1 1 2
1 2
4 4
2 1
3 3
Output:
2

Input:
4 4 3
1 1 2 0
1 1 0 1
1 0 1 1
0 1 1 2
3 1
1 3
4 4
Output:
3