The king of the Sky-Dragon Kingdom likes the trading of houses. If there are some houses on sell, he buys the houses and sells them with high price. If there are no houses on sell, he will buy some land to build houses and then sell them.
One day, the king buys some houses and wants to sell some of them as a house set together. And he wants the price of this set as high as possible.
Each house has its profit pi and cost ci that if we add a house into our house set, the price of the set will increase pi and decrease ci. Moreover, for some pair of house i and j, if we pick one of them, but not another, that is, we sell them separately, the price of the set will decrease Si,j.
And for some personal interest of the king, some houses must be included in the set to sell. Please write a program to help the king that gives pi, ci, 1 ≤ i ≤ N of his N houses, and the costs Si,j between some pair of houses. Please compute the highest price of a set of houses.
The first line of the input file contains an integer T (T ≤ 5) indicating the number of testcases. For each test case, the first line contains three integers N (1 ≤ N ≤ 200) and M, K (0 ≤ K ≤ N) represents the number of house, the number of pair that they have separation cost and the number of houses must be included in the set. Following N lines each has two positive integer
pi and ci (0 ≤ pi, ci ≤ 10000) . And next M lines each contains three integer i, j, Si,j (1 ≤ i, j ≤ N, 1 ≤ Si,j ≤ 10000) represent that there is a separation cost Si,j between house i and house j. Then there is one integer in each next K lines represent the number of houses must be included in the set.
For each test case, output the highest price of a set of house. Output 0 if there are no set with positive price