uva798測資A

Input:
3 2 2
2 1 1
2 1 2

5 2 2
2 1 1
4 1 2

10 10 2
2 5 5
1 10 5

4 4 2
2 2 2
4 2 1

6 4 2
2 2 2
2 2 4

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

8 8 4
1 8 2
1 6 4
1 4 4
1 2 4

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

100 100 3
1 99 99
1 1 100
1 99 1

8 7 8
1 8 1
1 7 1
1 6 2
1 6 1
1 5 1
1 3 3
1 3 2
1 3 1

32 32 10
1 32 16
1 16 16
1 16 8
1 8 8
1 8 4
1 4 4
1 4 2
1 2 2
1 2 1
2 1 1
Output:
11
56
4
46
11
290
16
16
8
320
40000