AE. 浮士德的 AI 作弊排查

    传统题 1000ms 256MiB

浮士德的 AI 作弊排查

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

题目描述

在边狱公司的巴士“梅菲斯托费勒斯”上,一次新生训练刚刚结束。为了排查使用 AI 违规完成训练的情况,学长把一批代码提交交给了浮士德分析。

正在抓算法竞赛中使用 AI 作弊的浮士德

正在抓算法竞赛中使用AI作弊的浮士德.jpg

浮士德从中整理出了 nn 份值得检查的记录。分析第 ii 份记录需要花费 tit_i 分钟,分析完成后可以获得 viv_i 点有效线索。在巴士抵达下一站之前,分析装置最多还能运行 TT 分钟。

对于每份记录,浮士德只能选择“完整分析一次”或“不分析”,不能只分析一部分,也不能重复分析同一份记录。选择的所有记录所需时间之和不能超过 TT。

请你计算浮士德最多可以获得多少点有效线索。

输入格式

第一行包含两个整数 nn 和 TT,分别表示待复核记录的数量和分析装置剩余的总运行时间。

接下来 nn 行,第 ii 行包含两个整数 tit_i 和 viv_i,分别表示分析第 ii 份记录所需的时间和能够获得的有效线索点数。

输出格式

输出一个整数,表示在总分析时间不超过 TT 的条件下能够获得的最大有效线索点数。

数据范围

  • 1≤n≤5001 \le n \le 500;
  • 1≤T≤1000001 \le T \le 100000;
  • 1≤ti≤T1 \le t_i \le T;
  • 1≤vi≤1091 \le v_i \le 10^9;
  • 所有输入均为整数。

答案可能超过 32 位有符号整数的范围。

样例 1

4 8
3 6
4 7
5 10
2 4
16

样例 1 解释

分析第 11 份和第 33 份记录共需要 3+5=83+5=8 分钟,可以获得 6+10=166+10=16 点有效线索。

样例 2

3 10
6 12
5 10
4 7
19

样例 2 解释

分析第 11 份和第 33 份记录共需要 1010 分钟,可以获得 1919 点有效线索。每份记录最多只能分析一次。

样例 3

3 10
6 100
5 49
5 49
100

样例 3 解释

只分析第 11 份记录可以获得 100100 点有效线索。浮士德不必恰好用完全部 1010 分钟。

2026级SYUCT-ACM新生第一次训练

未参加
状态
已结束
规则
XCPC
题目
31
开始于
2026-9-23 18:30
结束于
2026-10-15 22:30
持续时间
532 小时
主持人
参赛人数
125