Transport

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

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.

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