## BTCODE_D - Maximum Profit

no tags

Chakra is a young and dynamic entrepreneur, who is developing rapidly as a successful hotelier. He owns the Quickbyte chain of restaurants, 'M' of which are fully functional now. He divides each day into 'N' time slots. For each time slot 'j', in every restaurant 'i', there are Aij waiters and Bij customers. Being a quality conscious person, he wants each waiter to handle atmost one customer in a given time slot. Since he is really busy, in a day each restaurant is open only during one of the time slots. Since the hunger and demand for food varies during the day, the price which the customer is willing to pay varies, and is given by Cij for a restaurant 'i' during a time slot 'j'.

Given the values of Aij, Bij and Cij, find the maximum profit which Chakra can make in a day.

### Input

The first line of input contains an integer 't', denoting the number of test cases.
For each testcase, the first line contains 2 space separated integers 'M' and 'N'.
Each of the next 'M' lines contains 'N' integers. The jth integer on the ith line denotes the value of Aij
Each of the next 'M' lines contains 'N' integers. The jth integer on the ith line denotes the value of Bij
Each of the next 'M' lines contains 'N' integers. The jth integer on the ith line denotes the value of Cij

### Output

For each test case output one value, denoting the maximum profit which Chakra can make in a day.

More than one restaurant can be open during a given time slot.

### Example

```Input:
1
2 3
1 2 3
3 2 1
3 2 1
1 2 3
4 5 2
3 1 6

Output:
16

Constraints:
t <= 50
1 <= M,N <= 100
1 <= Aij, Bij <= 5000
0 <= Cij <= 10^9

```

Explanation:

Test case 1: By opening the first restaurant at time slot 2 and second restaurant at time slot 3, Chakra makes a profit = 2*5 + 1*6 = 16. Note that although there are 3 customers for the second restaurant at time slot 3, since there is only 1 waiter, only 1 customer can be served.