题目内容

在一项测试执行任务中，有 $n$ 个候选测试用例可用于覆盖测试点。任意两个测试用例覆盖的测试点互不重复，且每个测试用例至多执行一次。对于第 $i$ 个测试用例，其执行时间为 $t[i]$ 分钟，覆盖的测试点数量为 $p[i]$ 个。

选择测试用例时需要满足两个限制。第一，所有被选用例的总执行时间不得超过 $T$ 分钟。第二，执行时间大于 30 分钟的测试用例称为超长时间用例，被选中的超长时间用例总数不得超过 $m$ 个。

目标是找出一组满足上述限制的测试用例，使它们覆盖的测试点数量之和最大。若不选择任何测试用例，覆盖数量为 0。

约束条件：

• $n$ 的取值范围为 1 到 100。
• $T$ 的取值范围为 1 到 5000。
• $m$ 的取值范围为 1 到 100。
• 每个测试用例的执行时间 $t[i]$ 的取值范围为 1 到 60。
• 每个测试用例覆盖的测试点数量 $p[i]$ 的取值范围为 1 到 1000。

输入描述

输入的第一行包含三个整数 $n$、$T$、$m$，分别表示测试用例总数、允许的最大总执行时间和允许选中的最大超长时间用例数。 接下来共有 $n$ 行，每行包含两个整数，依次表示一个测试用例的执行时间和覆盖的测试点数量。

输出描述

输出一个整数，表示在满足所有限制条件下能够覆盖的最大测试点总数；该值可以为 0。

样例1

输入

4 60 2
20 30
25 20
35 50
40 60

输出

90

说明

选择执行时间为 20 分钟的用例和执行时间为 40 分钟的用例，总执行时间为 $20+40=60$ 分钟，满足不超过 60 分钟的限制。

该方案覆盖的测试点数量为 $30+60=90$。其中 40 分钟用例是超长用例，只选择了 1 个，未超过超长用例数限制 2。

其他可选组合例如 25 分钟和 35 分钟的用例，总时间为 $25+35=60$ 分钟，但覆盖数量只有 $20+50=70$，低于 90。

因此最大覆盖测试点数为 90。

样例2

输入

1 31 1
31 100

输出

100

说明

只有 1 个测试用例，执行时间为 31 分钟，覆盖 100 个测试点。

该用例执行时间 31 大于 30，属于超长时间用例；但总时间 $31 \le 31$，且超长用例数 $1 \le 1$，满足所有限制。

因此可以执行该用例，最大覆盖测试点数为 100。

样例3

输入

5 120 2
31 10
32 20
33 30
34 40
35 50

输出

90

说明

所有测试用例的执行时间都大于 30 分钟，因此它们全部属于超长用例。限制最多只能选择 2 个超长用例。

在只能选择 2 个超长用例的条件下，选择执行时间为 34 分钟和 35 分钟的两个用例，总执行时间为 $34+35=69$ 分钟，不超过 120 分钟。

它们覆盖的测试点数量为 $40+50=90$，是所有可选 2 个超长用例组合中最大的。

如果尝试选择更多超长用例，例如再加入执行时间为 33 分钟的用例，总时间仍不超过 120 分钟，但超长用例数会达到 3 个，超过限制 2，因此不能选择。

所以最大覆盖测试点数为 90。

样例4

输入

5 100 1
40 60
35 50
30 49
25 45
20 40

输出

154

说明

执行时间大于 30 分钟的用例有 40 分钟和 35 分钟两个，但超长用例数限制为 1，因此不能同时选择这两个超长用例。

最优选择为 40 分钟的超长用例，以及 30 分钟和 25 分钟两个普通用例。

总执行时间为 $40+30+25=95$ 分钟，不超过 100 分钟。覆盖测试点数量为 $60+49+45=154$。

如果选择 35 分钟超长用例与两个普通用例，例如 $35+30+25=90$ 分钟，覆盖数为 $50+49+45=144$，低于 154。

因此最大覆盖测试点数为 154。