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.

Example

Input:
1
3
1 2 3
1 1 1
2 2 2
3 3 3
Output:
14 

Constraints:

1<=T<=10
1<=N<=40
All other integers in input are positive and not greater than 100.