Hunger Games

Interview

Time limit3sMemory limit256 MB

Summary

Choose weapons within the sack weight limit to maximize total preference.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

When the Hunger Games begin, the participant from each district picks weapons out of the toolboxes. Every participant gets one sack, and each sack has a fixed weight limit. The total weight of the chosen weapons must not exceed that limit. There is only one copy of each weapon, so the same weapon cannot be packed twice.

Participants prefer different weapons. Maximize the total preference of the chosen weapons while staying within the weight limit.

Input

The first line contains an integer $T$ , the number of test cases ( $1 \le T \le 100$ ). The $T$ test cases follow.

Each test case consists of four lines. The first line contains an integer $N$ , the number of weapons ( $1 \le N \le 50$ ). The second line contains an integer $W$ , the capacity of the sack ( $1 \le W \le 5000$ ). The third line contains $N$ integers giving the weight of each weapon in order. The fourth line contains $N$ integers giving the participant's preference value of each weapon in the same order. Every weight and every preference value is an integer between 1 and 100.

Output

For each test case, print the maximum total preference value on its own line.

Examples7

Example 1

Input

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

Expected output

32
26

Example 2
Input
```
1
1
1
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
1
1
100
100
```
Expected output
```
0
```
Example 4
Input
```
1
5
5000
100 99 98 97 96
1 2 3 4 5
```
Expected output
```
15
```
Example 5
Input
```
1
3
10
6 5 5
7 5 5
```
Expected output
```
10
```

Example 6

Input

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

Expected output

Example 7

Input

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

Expected output