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
2017-01-28 18:40:41
silly mistake cost me 3 WA..
2016-07-07 19:18:52
long long everything -_-
a small hint- Each restaurant can be operated on any of the given N slots. For example, if need be, all restaurants can be opened in slot 2.. This line could have been mentioned a little more explicitly in the problem
2016-07-03 16:33:33
AC in One Go!!
2016-06-25 23:51:54
in one go! :)
2016-06-25 10:06:49
easy one if getting WA focus on "Each of the next 'M' lines contains 'N' integers. The jth integer on the ith line denotes the value of Aij ",
" For each time slot 'j', in every restaurant 'i', there are Aij waiters"
2015-07-18 16:20:38
take long long int for money... it cost me 1 WA...
2014-07-07 13:11:36 j1k7_7(JaskamalKainth)
1st attempt.
Simplest problem.:D
2014-06-24 19:15:42 fanatique
in a single slot any no.of restaurants can be functional..
2013-10-21 09:44:55 Himanshu
A silly mistake cause me 4 WA I think one restaurant can be open in a single slot
2013-08-20 15:07:22 Pallav Roy
first code using structure.. :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.