P6770: 小奇采药
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
【题目描述】
小奇是只天资聪颖的喵，他的梦想是成为世界上最伟大的医师。
为此，他想拜喵星球最有威望的医师为师。
医师为了判断他的资质，给他出了一个难题。
医师把他带到一个到处都是草药的山洞里对他说：
“小奇，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。
我会给你一段时间，在这段时间里，你可以采到一些草药。
如果你是一只聪明的喵，你应该可以让采到的草药的总价值最大。”
【输入格式】
第 1 行包括 1 个整数 T ，表示数据组数。
对于每组数据，第 1 行包括 2 个整数，n，m，表示草药的数目和能用于采药的时间。
接下来 n 行，每行两个整数 ti,vi。
保证 m,ti,vi 在限制范围内均匀随机生成。
【输出格式】
输出 T 行，每行 1 个数字，表示每组数据答案。
【输入样例】
1
3 70
71 100
69 1
1 2
【输出样例】
3
【数据范围与提示】
对于
30%数据，
1≤
n≤
20，1≤
m,vi,ti≤
10^4；
对于
60%数据，
1≤
n≤
100，1≤
m,vi,ti≤
10^5；
对于
100%数据，
1≤
T≤
100，1≤
n≤
150，1≤
m,vi,ti≤
10^9。