1759: Power Line

While DUT is hosting this NECPC Contest, in order to control the expenditure, careful considerations should be given in many respects, such as the layout of the contest venue. When the contest venue is arranged, each computer requires power input. While the layout of computers and power-points are already fixed, some lines have to be purchased to link the computers with power-points. And, Raven finds out that it is cheaper to buy power lines of the same length than to buy lines of different lengths, so he would buy all the lines with the same length. If Raven wants to save money, would you help him?

The first line of the input contains an integer T, which indicates the number of test cases. For each test case, there are three positive integers in the first row, n, m, p( 0 <= n,m <= 200，0 < p < 100 ). It means that there are n computers and m power-points. The power line costs ￥p per unit. In the following n rows, i-th line has m positive integers indicating the distances between the i-th computer and all the power points. The distance is less than 10000. In the last row, there are m positive integers, ci ( 0 < ci < 5, 0 <= i < m ), showing No.i power-point can provide power to ci computers in total.

For each case, if the layout of computers and power lines are not reasonable, which means you cannot provide power to every computer, just output -1. Otherwise, output the lowest total price for power lines.

1
2 2 1
1 3
2 2
1 1

4

You many link the first computer with the first power-points, and link the second computer with the second power-points. This will cost 4(2*2).