드론 적재

시간 제한2초메모리 제한512 MB

요약

무게 한도가 각각 다른 두 드론에 물건을 나누어 싣되 물건을 자르거나 공유할 수 없을 때 얻을 수 있는 최대 가치를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

북극 배송 센터가 썰매를 접고 드론 배송으로 바꾼다. 첫 시범 운행에 나서는 드론은 두 대뿐이고, 드론마다 실을 수 있는 무게에 한계가 있다.

선물 후보 목록이 주어진다. 선물마다 무게와 가치가 있고, 가치는 천 달러 단위의 정수다. 두 드론에 나누어 실을 선물을 골라서 실어 나르는 가치의 합을 최대로 만들어라. 선물은 쪼갤 수 없고, 한 선물을 두 드론에 나누어 실을 수도 없다. 고르지 않고 남겨 두는 선물이 있어도 된다.

한 드론에 실은 선물 무게의 합은 그 드론의 한계 이하여야 한다. 이때 얻을 수 있는 가치의 최댓값을 구하라.

입력

입력은 여러 개의 문제로 이루어진다. 첫 줄에 문제의 개수 $P$ ( $1 \le P \le 10$ )가 주어진다.

이어서 문제마다 세 줄이 주어진다. 첫 줄에는 선물 후보의 개수 $N$ ( $1 \le N \le 100$ )과 두 드론의 적재 한계 $W_1$ , $W_2$ ( $1 \le W_1, W_2 \le 1000$ )가 주어진다. 둘째 줄에는 각 선물의 무게 $w_i$ ( $1 \le w_i \le 100$ )가 $N$ 개 주어진다. 셋째 줄에는 각 선물의 가치 $v_i$ ( $1 \le v_i \le 100$ )가 $N$ 개 주어진다. 한 줄 안의 수는 공백 하나로 구분하며, 줄의 앞뒤에 공백은 없다.

출력

문제마다 한 줄씩 출력한다. 줄의 형식은 Problem , 문제 번호(1부터 센다), : , 두 드론이 실어 나른 선물 가치의 합의 최댓값 순서다.

첫 번째 문제의 답이 22이면 Problem 1: 22을 출력한다.

예제6

예제 1

입력

2
4 9 4
3 4 5 6
5 7 9 10
6 9 11
3 4 5 6 3 4
2 3 4 5 3 3

예상 출력

Problem 1: 22
Problem 2: 16

예제 2
입력
```
1
1 2 3
5
100
```
예상 출력
```
Problem 1: 0
```
예제 3
입력
```
1
1 2 5
5
100
```
예상 출력
```
Problem 1: 100
```
예제 4
입력
```
1
2 9 3
5 7
10 13
```
예상 출력
```
Problem 1: 13
```
예제 5
입력
```
1
1 1 1
1
1
```
예상 출력
```
Problem 1: 1
```

예제 6

입력

예상 출력

Problem 1: 10