Animesh practices some programming contests

All submissions for this problem are available.
As you know, Malvika has created some n programming contests. Each of the contests has three problems, categorized as easy, medium and hard on difficulty level. For the i^{th} contest, easy problem takes TE[i] hours and gives you PE[i] pleasure. Similarly, medium problem takes TM[i] hours, gives PM[i] pleasure, and a hard one has the values TH[i], PH[i].
Today, Animesh wanted to practice some of them. Animesh has a really bad habit of trying problems for only a few minutes and saying to Malvika "I am a noob, you are a pro. It's some weird shit I don't know. Please, tell me the solution, bro!" Having been irritated by this behaviour numerous times in the past, she granted him K special powers he can use before starting the practice session. By using a single power, Animesh can pick any two problems irrespective of their difficulty from two different contests and swap them.
Animesh has at max time hours before he gets frustrated by his noobness and ends the practice session. He wants to make the maximum use of it by getting as much pleasure out of this activity as possible. Animesh also gets bored with the contest themes fairly quickly, so he does not want to solve more than one problem from any contest. Can you help Animesh in estimating the maximum amount of pleasure he can achieve out of this activity?
Input
 The first line of input contains a single integer T denoting number of test cases
 For each test case :
 The first line contains three space separated integers n, k, time.
 Each of the next n lines contain three space separated integers denoting TE[i], TM[i], TH[i].
 Each of the next n lines contain three space separated integers denoting PE[i], PM[i], PH[i].
Output
 For each test case, output a single integer in a separate line corresponding to the answer of the problem.
Constraints
 1 ≤ T ≤ 10
 1 ≤ n ≤ 50
 0 ≤ k ≤ n * n
 1 ≤ time ≤ 50
 1 ≤ TE[i], TM[i], TH[i] ≤ 50
 1 ≤ PE[i], PM[i], PH[i] ≤ 100000
Example
Input: 2 1 0 5 1 2 3 5 3 6 2 1 6 1 2 1 2 3 3 5 3 3 4 6 5 Output: 6 11
Explanation
In the first example, Malvika has prepared only one programming contest, its easy problem takes 1 hour and gives 5 units of pleasure. The medium one takes 2 hours and gives 3 units of pleasure whereas the same values for hard are 3 hours and 6 units of pleasure. Animesh has only 5 hours and can select at max one problems out of these to solve. The hard problem is the best candidate to choose for him, it will him give him 6 units of pleasure and take his 5 hours. So, the answer is 6.
In the second example, Malvika has prepared two programming contests.
 First programming contest:
 Easy problem — 1 hour and 5 units of pleasure.
 Medium problem — 2 hours and 3 units of pleasure.
 Hard problem — 1 hours and 3 units of pleasure.
 Second programming contest:
 Easy problem — 2 hours and 4 units of pleasure.
 Medium problem — 3 hours and 6 units of pleasure.
 Hard problem — 3 hours and 5 units of pleasure.
Author:  admin2 
Tags  acm15chn, admin2, dynamicprogramming 
Date Added:  15012016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 