Give out candies

Problem Description

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.

Sample Input

2

2 1 1

1

1

1 2 1

3 3 2

1 2 3

2 3 1

3 1 2

1 2 0

2 3 0

Sample Output

2

7

Source

2017 Multi-University Training Contest - Team 7

https://acm.hdu.edu.cn/showproblem.php?pid=6126