BTCODE_D - Maximum Profit

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 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 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.

Constraints

t <= 50

1 <= M,N <= 100

1 <= Aij, Bij <= 5000

0 <= Cij <= 10^9

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.


Added by:suhash
Date:2011-02-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2011, NIT Trichy, India

hide comments
2012-04-10 21:26:54 maaz
Long long int cannot be used for representing index of an array
give runtime error be careful..
Otherwise Tutorial Problem
2012-04-10 10:51:07 Aradhya
tutorial.. for kids :D
2011-12-18 12:57:13 xyz
getting wa.. more test cases please
2011-04-15 13:33:21 Aman
input output specs are wrong Cij exceeds 10^9
2011-02-27 12:41:41 Mohamed Maher
hint : use long long for cij in c/c++
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.