Transport

Interview

Time limit1sMemory limit128 MB

Summary

With at most 20 items, choose a subset whose total weight is at most W and whose total value is as large as possible.

Level: Medium4 of 10
Topics: Brute force, Backtracking, Dynamic programming
Solved: No attempts yet

Problem

You have a transport plane that must deliver items to a remote location. You would like to load all of the items, but you cannot exceed the plane's weight capacity $W$ . Given $n$ items with known weights $w_1, w_2, \dots, w_n$ and values $v_1, v_2, \dots, v_n$ , find the most valuable subset of the items that fits into the plane without exceeding the capacity $W$ .

Input

The first line contains a positive integer indicating the number of problem sets. Each problem set begins with a line containing two positive integers $n$ and $W$ , where $n$ is the number of items and $W$ is the capacity of the plane. The next $n$ lines each contain two integers $w$ and $v$ , where $w$ is the weight and $v$ is the value of an item. All weights and values are positive integers, and the number of items in any problem set is at most 20.

Output

For each problem set, print on its own line the total value of the most valuable subset that the plane can transport without exceeding its capacity $W$ .

Examples3

Example 1

Input

Expected output

6
65

Example 2
Input
```
1
1 10
5 100
```
Expected output
```
100
```
Example 3
Input
```
1
1 3
5 100
```
Expected output
```
0
```