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 × 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 i-th 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. Input The first line of the input contains the number of test cases t (1 ≤ t ≤ 10). 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 i-th integer of the j-th line is the height of square (xi,yj). Heights are integers between 0 and 100. Output For each test case, print on a single line the least number of magic needed. Sample Input 3 4625 1115414533 121261321361431 326135 217446 231434 434323 4337 11121341424311 111211221231311321331 111 222 333 444
2/2 8 11 3 7 11151981858945 1 3 1 1 7 1 1 11 1 4 5 1 8 3 1 8 7 1 8 11 1 92319231923 11111111111 99999999999 11111111111 99999999999 11111111111 99999999999 18791879187 Sample Output 1 0 2