헝거 게임

면접 대비

시간 제한3초메모리 제한256 MB

요약

무게 제한을 넘지 않게 무기를 골라 선호도 합을 최대로 합니다.

난이도: 쉬움10점 중 3점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

헝거 게임이 시작되면 각 구역의 참가자는 도구 상자에서 무기를 골라 담는다. 참가자에게는 자루가 하나씩 주어지고, 자루마다 담을 수 있는 무게의 한계가 정해져 있다. 그래서 고른 무기의 무게 합은 자루의 한계를 넘을 수 없다. 무기는 종류마다 하나씩만 있으므로 같은 무기를 두 번 담을 수 없다.

참가자마다 선호하는 무기가 다르다. 무게 한계를 지키면서 고른 무기의 선호도 합을 최대로 만들어라.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다 ( $1 \le T \le 100$ ). 이어서 $T$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스는 네 줄로 이루어진다. 첫째 줄에 무기의 개수 $N$ 이 주어진다 ( $1 \le N \le 50$ ). 둘째 줄에 자루의 용량 $W$ 가 주어진다 ( $1 \le W \le 5000$ ). 셋째 줄에 각 무기의 무게를 나타내는 $N$ 개의 정수가 순서대로 주어진다. 넷째 줄에 각 무기에 대한 참가자의 선호도를 나타내는 $N$ 개의 정수가 같은 순서로 주어진다. 무게와 선호도는 모두 1 이상 100 이하의 정수이다.

출력

각 테스트 케이스마다 얻을 수 있는 선호도 합의 최댓값을 한 줄에 하나씩 출력한다.

예제7

예제 1

입력

2
8
20
2 3 4 5 5 5 5 9
3 4 5 8 8 8 8 10
5
20
2 3 4 5 9
3 4 5 8 10

예상 출력

32
26

예제 2
입력
```
1
1
1
1
1
```
예상 출력
```
1
```
예제 3
입력
```
1
1
1
100
100
```
예상 출력
```
0
```
예제 4
입력
```
1
5
5000
100 99 98 97 96
1 2 3 4 5
```
예상 출력
```
15
```
예제 5
입력
```
1
3
10
6 5 5
7 5 5
```
예상 출력
```
10
```

예제 6

입력

1
50
5000
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

예상 출력

예제 7

입력

1
50
4999
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7

예상 출력