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 $w_{i,j}$ satisfaction score, now you need to help HazelFan maximize the sum of the satisfaction scores of these children.
Input
The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases.
For each test case:
The first line contain three positive integers $n,m,k(1\leq n,m\leq50,1\leq k\leq150)$.
The next $n$ lines, the $i$th line contains $m$ positive integers, the $j$th integer denotes $w_{i,j}$.
The next $k$ lines, each line contains three integers $x,y,z(1\leq x,y\leq n,\mid z\mid<233)$, denoting a piece of requirement.
Output
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.