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 A_ij waiters and B_ij customers. Being a quality conscious person, he wants each waiter to handle at most 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 C_ij for a restaurant 'i' during a time slot 'j'.

Given the values of A_ij, B_ij and C_ij, 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 j^th integer on the i^th line denotes the value of A_ij.

Each of the next 'M' lines contains 'N' integers. The j^th integer on the i^th line denotes the value of B_ij.

Each of the next 'M' lines contains 'N' integers. The j^th integer on the i^th line denotes the value of C_ij

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.

Constraints

t ≤ 50

1 ≤ M,N ≤ 100

1 ≤ A_ij, B_ij ≤ 5000

0 ≤ C_ij ≤ 10⁹

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

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.