시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB113968383.838%

문제

After doing some digging on the beach, you happen to pull up an old treasure chest! It is full of rare artefacts worth a lot of money! Unfortunately, you can only carry so much with you back to your boat before the tide washes the treasure chest away. Write a program that will calculate the highest total item value that you can take back in one trip, given several item weights and values, and your carrying capacity.

입력

The first line will contain a single integer n that indicates the number of data sets that follow. Each data set will start with two integers i w that indicate the number items that follow and your carrying capacity, respectively. The next i lines will each have two numbers, the value of each item and its weight.

출력

Output the highest value that you can carry in one trip for each data set.

예제 입력 1

2
5 50
70 10
90 32
40 4
150 45
60 46
1 10
500000 11

예제 출력 1

200
0