Animesh practices some programming contests

Malvika has created n programming contests. Each contest has three problems, categorized as easy, medium, and hard. For the i-th contest, the easy problem takes $TE_i$ hours and gives $PE_i$ pleasure. The medium problem takes $TM_i$ hours and gives $PM_i$ pleasure. The hard problem takes $TH_i$ hours and gives $PH_i$ pleasure.

Today, Animesh wants to practice some of them. He has a bad habit of trying problems for only a few minutes and then telling Malvika "I am a noob, you are a pro. It's some weird shit I don't know. Please, tell me the solution, bro!" Malvika got irritated by this many times, so she granted him $K$ special powers he can use before starting the practice session. With one power, Animesh can pick any two problems, regardless of difficulty, from two different contests and swap them.

Animesh has at most $time$ hours before he gets frustrated and ends the session. He wants to get as much pleasure as possible in that time. He also gets bored with contest themes quickly, so he does not want to solve more than one problem from any contest. Find the maximum amount of pleasure Animesh can get.

The first line contains a single integer $T$, the number of test cases.

For each test case, the first line contains three space-separated integers $n$, $k$, and $time$. The next $n$ lines each contain three space-separated integers $TE_i$, $TM_i$, $TH_i$. The following $n$ lines each contain three space-separated integers $PE_i$, $PM_i$, $PH_i$.

For each test case, output a single integer on its own line, the answer to the problem.

• $1 \le T \le 10$
• $1 \le n \le 50$
• $0 \le k \le n^2$
• $1 \le time \le 50$
• $1 \le TE_i, TM_i, TH_i \le 50$
• $1 \le PE_i, PM_i, PH_i \le 100000$

In the first example, Malvika has prepared only one contest. Its easy problem takes 1 hour and gives 5 units of pleasure. The medium problem takes 2 hours and gives 3 units. The hard problem takes 3 hours and gives 6 units. Animesh has only 5 hours and can solve at most one of these problems. The hard problem is the best choice, since it gives him 6 units of pleasure and takes his 5 hours. So the answer is 6.

In the second example, Malvika has prepared two contests.

First contest: easy takes 1 hour and gives 2 units, medium takes 2 hours and gives 3 units, hard takes 1 hour and gives 3 units.

Second contest: easy takes 2 hours and gives 4 units, medium takes 3 hours and gives 6 units, hard takes 3 hours and gives 5 units.

Animesh has 6 hours and can use the special power at most once. He swaps the medium problem of the second contest with any problem of the first contest. Then he can select the two problems that take 3 hours each and give 6 and 5 units, for a total of 11 units.