当前没有测试数据。

题目描述

Rowlet is playing a very popular game in the pokemon world. Recently, he has encountered a problem and wants to ask for your help. In this game, there is a technology tree system. There are n kinds of technology in this game, each of them has m levels numbered from 1 to m. In the beginning, all technologies have no level (regard as level 0). When the i-th technology is at the (j - 1)-th level, the player can pay $c_{i j}$​ pokedollars (currency used in this game) to upgrade this technology into the j-th level. However, sometimes upgrading is so easy that the cost might be negative, which implies the player may gain profit from upgrading technologies. Moreover, if all technologies have been upgraded to level j, the player will gain an additional profit of djd_{j}dj​ pokedollars. However, sometimes too many technologies of the same level might be confusing, hence the profit can be negative as well. Rowlet wants to determine the optimal strategy that can bring him the most pokedollars. Help him to find the maximum gain. Note that Rowlet may upgrade nothing, and in that case, the profit is zero.

输入格式

There are multiple test cases. The first line contains an integer T ($1 \leq T \leq 10$), indicating the number of test cases. Test cases are given in the following.For each test case, the first line contains two integers n, m ($1 \leq n, m \leq 1000$), representing the number of technologies and the number of levels respectively.The i-th of the next n lines contains m integers, where the j-th number is $c_{i j}$​ ($-10^{9} \leq c_{i j} \leq 10^{9}$).The last line contains m integers, where the j-th number is $d_{j}$ ($-10^{9} \leq d_{j} \leq 10^{9}$).We ensure that the sum of $n \cdot m$ in all test cases is at most $2 \times 10^{6}$.

输出格式

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer(in pokedollars) to this test case.

样例

样例输入 1

2
2 2
1 2
2 -1
4 1
3 3
1 2 3
1 2 3
1 2 3
6 7 8

样例输出 1

Case #1: 2
Case #2: 4

数据范围与提示

In the first example, Rowlet can upgrade the first technology to level 1 and the second technology to level 2, which costs 1 + 2 - 1 = 2 pokedollars, but Rowlet can get 4 pokedollars as the bonus of upgrading all technologies to level 1, so the answer is 4 - 2 = 2 pokedollars. In the second example, Rowlet can upgrade all technologies to level 2, which costs $1\times3 + 2\times3=9$ pokedollars, but Rowlet can get 6 pokedollars as the bonus of upgrading all technologies to level 1 and 7 pokedollars as the bonus of upgrading all technologies to level 2, so the answer is 6 + 7 - 9 = 4 pokedollars.