Gitu is the smartest economist in the city. He has been kidnapped by Ankur and Vaibhav. They want him to make profit by Arbitrage.

Arbitrage, roughly, is the process of taking advantage of price differences in various economies/markets to earn profit.

So Ankur and Vaibhav have some units of each of the N valuables items to be sold in exactly N different markets in exchange of some money. Now they want Gitu to sell the items intelligently and maximize the total money earned. However, there is one condition. If Gitu sells some units of a particular item in a particular market, he cannot sell further units of that item in any other market and he cannot sell any other item’s units in this market.

Ankur and Vaibhav have allowed Gitu to talk to you and only you. Can you help Gitu to strategize the sell to make maximum earning?

Input

First line consists of T, the number of test cases.

Each test case starts with an integer N, the different items to be sold and the different markets present.

Next line contains N space separated integers, the units of each of the items Ankur and Vaibhav have.

Each of the next N lines consists of N space separated integers. jth integer in ith line signifies the money earned after selling one unit of jth item in ith market.

Output

Output T lines corresponding to each test case, the maximum money that can be earned by following the process stated above.

Constraints

1 ≤ T ≤ 10

1 ≤ N ≤ 40

All other integers in input are positive and not greater than 100.

Example

Input:
1
3
1 2 3
1 1 1
2 2 2
3 3 3

Output:
14