解题思路

这是一个带额外约束的 0/1 背包问题。

• 每个测试用例只能选一次：典型 0/1 背包
• 总执行时间不能超过 T：背包容量是时间
• 若 t[i] > 30，则为“超长时间用例”，被选中的超长用例数量不超过 m：再加一维“超长数量”限制
• 目标：最大化覆盖测试点总数（价值）

题目内容

执行测试用例时，需要在有限的时间内尽可能多地覆盖测试点。

已知：

• 共有 $n$ 个测试用例，第 $i$ 个测试用例的执行时间为 $t[i]$ 分钟，覆盖的测试点数量为 $p[i]$ 个

• 每个用例只能执行一次，每个用例覆盖的测试点不同

• 如果一个用例的执行时间超过 $30$ 分钟，则属于超长时间用例，执行的所有超长时间用例数不超过 $m$

请问在限定的时间 $T$ 内，执行的用例所能覆盖的最大测试点数量。

输入描述

第 1 行：$n\ T\ m$，代表 $n$ 个测试用例，范围 $[1,100]$，最大执行时长为 $T$，范围 $[1,5000]$；最大超长时间用例数为 $m$，范围 $[1,100]$

第 2 行：$t[0]\ p[0]$，代表第 1 个用例的执行时间和测试点数量，$t[i]$ 范围 $[1,60]$，$p[i]$ 范围 $[1,1000]$

第 $n+1$ 行：$t[n-1]\ p[n-1]$，代表第 $n$ 个用例的执行时间和测试点数量，$t[i]$ 范围 $[1,60]$，$p[i]$ 范围 $[1,1000]$

输出描述

第1行：$k$，输出最大的测试点覆盖数量，可以是0

样例1

输入

3 50 0
35 5
40 10
50 15

输出

0

说明

输入表示：$n=3，T=50，m=0$ 所有用例均是超长时间用例，不能选择，输出$0$

样例2

输入

3 10 1
15 5
20 10
25 15

输出

0

说明

输入表示：$n=3，T=10，m=1$ 所有用例时间均超过最大时间，输出$0$

样例3

输入

4 100 1
20 50
35 60
25 30
40 70

输出

150

说明

输入表示：$n=4，T=100，m=1$ 选择用例$0,2,3$，总时间为$20+25+40=85<100$，超长用例$1<=1$，最大测试点数量$50+30+70=150$