There are n children numbered 1 to n, and HazelFan's task is to give out candies to the children. Each children must be given at least 1 and at most m candies. The children raised k pieces of requirements, and every piece includes three integers x,y,z, means that the number of candies given to the child numbered x, subtract the number of candies given to the child number y, the result should not be more than z. Besides, if the child numbered i is given j candies, he or she will get wi,jsatisfaction score, now you need to help HazelFan maximize the sum of the satisfaction scores of these children.

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
The first line contain three positive integers n,m,k(1≤n,m≤50,1≤k≤150).
The next n lines, the ith line contains m positive integers, the jth integer denotes wi,j.
The next k lines, each line contains three integers x,y,z(1≤x,y≤n,∣z∣<233), denoting a piece of requirement.

For each test case:
A single line contains a nonnegative integer, denoting the answer. Particularly, if there is no way to give out candies, print -1.