16 人解决，26 人已尝试。
31 份提交通过，共有 111 份提交。
5.7 EMB 奖励。
2113. WY II
单点时限: 4.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.
But after the “Training of Lord Fish’s Fan I”, WY finally realized that he cannot improve himself by solving easy problems. So he finds some valuable problems, and starts another training.
输入格式
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 N 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 1 <= k <= 10^7, means WY must spend t units of time to solve this problem, and he can learn k units of knowledge after solving it. As you can imagine, valuable problems are very hard to find. So WY can only find at most 30 of them. That is to say, 1 <= N <= 30.
输出格式
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 10000000 2500000 10000000 2500000 10000000 2500000 10000000
Output
30 0 11 40000000 Hint Sample 0: WY can solve all three problems and get 10+10+10 = 30 units of knowledge. Sample 1: He can solve neither of these problems. Sample 2: The best choice is to solve the second one. Sample 3: Finally, WY doesn't spend his time meaningless :D.
题目标签