Deadlock Detection

Example

Input

2 2 7 3 4 3 2 1 3 1 1 2 2 1 2 2 1 1 2 2 2 1 1

Output

5

inputFormat

Input

2 2 7 3 4 3 2 1 3 1 1 2 2 1 2 2 1 1 2 2 2 1 1

outputFormat

Output

5

样例

2 2 7
3 4
3 2
1 3
1 1
2 2
1 2
2 1
1 2
2 2
1 1

5