Alan's father has bought him a box of toy soldiers, k red soldiers, k green soldiers, and one gold
soldier. There is a m x n board, each square has a height hi,j, and all squares are big
enough to hold all the soldiers. At first, each soldier is placed in a square (not neccesarily all different), and t goal squares are chosen, each assigned with an 'importance value' ri. The goal is to move soldiers on these t squares so that the ith square has exactly ri soldier(s) on it. Each soldier
has to be on one of the t squares, so it's guaranteed that the sum of all ri is equal to 2k+1.
Each time, a soldier can move to an adjacent(north, south, east or west) square, but it can't move outside the board.
Red soldiers can only climb up, so it can move only if the target square is not lower than the current square; Green soldiers
can only jump down, so it can move only if the target square is not higher than the current square; The gold soldier can move
freely on the board.
Since it may be impossible to achieve the goal, Alan is allowed to use a kind of magic. Every time he uses the magic, he can
do a permutation of all the soldiers(that is, he can do an arbitary number of exchanges, but he cannot move any soldier).
Help Alan to use least possible number of magic to achieve the goal.
The first line of the input contains the number of test cases t. Each test case begins with a line
containing 4 integers m, n, k, t (2<=m,n<=100, 1<=k<=50, 1<=t<=2k+1). The second line
contains 2k+1 pairs (xi,yi) indicating the initial positions of the soldiers. The first k
pairs describe red soldiers, the following k describe the green soldiers, and the last one describe the gold soldier.
The third line contains t triples (xi,yi,ri) indicating the positions and importance
value of the goal squares. The following m lines each contains n integers, indicating the heights of squares. The ith
integer of the jth line is the height of square (xi,yj). Heights are integers between 0 and 100.
For each test case, print on a single line the least number of magic needed.
3 4 6 2 5 1 1 1 5 4 1 4 5 3 3 1 2 1 2 6 1 3 2 1 3 6 1 4 3 1 3 2 6 1 3 5 2 1 7 4 4 6 2 3 1 4 3 4 4 3 4 3 2 3 4 3 3 7 1 1 1 2 1 3 4 1 4 2 4 3 1 1 1 1 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 1 1 1 1 2 2 2 3 3 3 4 4 4 8 11 3 7 1 1 1 5 1 9 8 1 8 5 8 9 4 5 1 3 1 1 7 1 1 11 1 4 5 1 8 3 1 8 7 1 8 11 1 9 2 3 1 9 2 3 1 9 2 3 1 1 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 9 9 9 9 1 8 7 9 1 8 7 9 1 8 7
1 0 2
Migrated from old NTUJ.
UVa 10418
| No. | Testdata Range | Score |
|---|