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 A_{ij} waiters and B_{ij} 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 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.
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 <= A_{ij}, B_{ij} <= 5000 0 <= C_{ij} <= 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.
hide comments
vengatesh15:
20170128 18:40:41
silly mistake cost me 3 WA.. 

akshayvenkat:
20160707 19:18:52
long long everything _


baadshah_:
20160703 16:33:33
AC in One Go!! 

visvats_141095:
20160625 23:51:54
in one go! :) 

vineetpratik:
20160625 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 ",


anuveshkothari:
20150718 16:20:38
take long long int for money... it cost me 1 WA... 

j1k7_7(JaskamalKainth):
20140707 13:11:36
1st attempt.


fanatique:
20140624 19:15:42
in a single slot any no.of restaurants can be functional.. 

Himanshu:
20131021 09:44:55
A silly mistake cause me 4 WA I think one restaurant can be open in a single slot 

Pallav Roy:
20130820 15:07:22
first code using structure.. :D 
Added by:  suhash 
Date:  20110226 
Time limit:  0.270s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Bytecode 2011, NIT Trichy, India 