Animesh가 프로그래밍 대회 일부를 연습하는 문제

Malvika는 $n$개의 프로그래밍 대회를 만들었다. 각 대회에는 쉬움, 보통, 어려움으로 나뉜 문제가 하나씩 있다. $i$번째 대회의 쉬운 문제는 $TE_i$시간이 걸리고 $PE_i$만큼의 즐거움을 준다. 보통 문제는 $TM_i$시간이 걸리고 $PM_i$만큼의 즐거움을 준다. 어려운 문제는 $TH_i$시간이 걸리고 $PH_i$만큼의 즐거움을 준다.

오늘 Animesh는 이 중 일부를 연습하려고 한다. 그는 문제를 몇 분만 풀어보고 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는 연습을 시작하기 전에 쓸 수 있는 특수 능력 $K$개를 그에게 주었다. 능력 하나로 Animesh는 서로 다른 두 대회에서 난이도와 관계없이 문제 두 개를 골라 서로 바꿀 수 있다.

Animesh는 좌절해서 연습을 끝내기 전까지 최대 $time$시간을 쓸 수 있다. 그 시간 안에서 최대한 많은 즐거움을 얻고 싶어 한다. 또한 대회 주제에 금방 싫증을 내서, 한 대회에서 문제를 두 개 이상 풀고 싶어 하지 않는다. Animesh가 얻을 수 있는 즐거움의 최댓값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 정수 $n$, $k$, $time$이 주어진다. 다음 $n$줄에는 각각 공백으로 구분된 정수 $TE_i$, $TM_i$, $TH_i$가 주어진다. 그다음 $n$줄에는 각각 공백으로 구분된 정수 $PE_i$, $PM_i$, $PH_i$가 주어진다.

각 테스트 케이스마다 답을 정수 하나로 한 줄에 출력한다.

• $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$

첫 번째 예시에서 Malvika는 대회를 하나만 준비했다. 그 쉬운 문제는 1시간이 걸리고 즐거움 5를 준다. 보통 문제는 2시간이 걸리고 즐거움 3을 준다. 어려운 문제는 3시간이 걸리고 즐거움 6을 준다. Animesh에게는 5시간뿐이고, 이 중 최대 한 문제만 풀 수 있다. 어려운 문제가 5시간 안에 즐거움 6을 주므로 가장 좋은 선택이다. 따라서 답은 6이다.

두 번째 예시에서 Malvika는 대회를 두 개 준비했다.

첫 번째 대회: 쉬운 문제는 1시간에 2, 보통 문제는 2시간에 3, 어려운 문제는 1시간에 3을 준다.

두 번째 대회: 쉬운 문제는 2시간에 4, 보통 문제는 3시간에 6, 어려운 문제는 3시간에 5를 준다.

Animesh에게는 6시간이 있고 특수 능력은 최대 한 번 쓸 수 있다. 두 번째 대회의 보통 문제를 첫 번째 대회의 아무 문제와 바꾼다. 그러면 3시간짜리 문제 두 개를 고를 수 있고, 즐거움 6과 5를 얻어 합계 11이 된다.