传统题 1000ms 256MiB

小奇采药

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小奇是只天资聪颖的喵,他的梦想是成为世界上最伟大的医师。

为此,他想拜喵星球最有威望的医师为师。

医师为了判断他的资质,给他出了一个难题。

医师把他带到一个到处都是草药的山洞里对他说:

“小奇,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。

我会给你一段时间,在这段时间里,你可以采到一些草药。

如果你是一只聪明的喵,你应该可以让采到的草药的总价值最大。”

输入格式

11 行包括 11 个整数 TT ,表示数据组数。

对于每组数据,第 11 行包括 22 个整数,nmn,m,表示草药的数目和能用于采药的时间。

接下来 nn 行,每行两个整数 ti,vit_i,v_i,表示需要的时间和价值。

保证 m,ti,vim,t_i,v_i 在限制范围内均匀随机生成。

输出格式

输出 TT 行,每行 11 个数字,表示每组数据答案。

样例

1
3 70
71 100
69 1
1 2
3

数据范围与提示

对于 30%30\% 数据,1n20,1m,vi,ti1041\leq n\leq 20,1 \leq m,v_i,t_i\leq 10^4
对于 60%60\% 数据,1n100,1m,vi,ti1051\leq n\leq 100,1 \leq m,v_i,t_i\leq 10^5
对于 100%100\% 数据,$1\leq T\leq 10,1 \leq n \leq 150,1\leq m,v_i,t_i\leq 10^9$。

搜索剪枝

未认领
状态
已结束
题目
8
开始时间
2024-4-1 0:00
截止时间
2024-4-30 23:59
可延期
24 小时