**25 人解决**，50 人已尝试。

**32 份提交通过**，共有 156 份提交。

**5.9** EMB 奖励。

**单点时限: **3.0 sec

**内存限制: **256 MB

As eveyone known, WY is the most faithful fan of Lord fishcanfly. The power of Lord fish is too great to reach, but WY decides to train himself to near the Lord as much as he can. He even makes a slogan as follows:

So WY wants to AC many problems. But he has only a little time :(, so he cannot solve all of them. He needs the help of other Lord Fish’s fans to make a plan to do most training without exceeding the time limit. Of course, it’s useless to solve the same problem two or more times, because he can only learn knowledge at the first time.

Input contains multiple test case. The first line is T, the number of test case, then T case follows. Each test case begins with two integers 1 <= N <= 100 and 1 <= L <= 10^9, which denote the number of problems and the time WY can spend at most. The following N lines each represents a problem with two positive integers 1 <= t <= 10^7 and k, means WY must spend t units of time to solve this problem, and he can learn k units of knowledge after solving it. Because of the bad habit of WY, he is interested in solving easy problems. That is to say, he cannot learn much knowledge once. So each k is no greater than 200.

For each test case, print an integer which is the most number of units of knowledge WY can learn after the training.

Input

4 3 100 10 10 20 10 30 10 2 50 60 100 51 90 2 50 40 10 49 11 4 10000000 2500000 1 2500000 1 2500000 1 2500000 1

Output

30 0 11 4

**25 人解决**，50 人已尝试。

**32 份提交通过**，共有 156 份提交。

**5.9** EMB 奖励。

题目标签