小红正在一座神秘遗迹中收集宝藏。遗迹中共有 件宝藏,第 件宝藏需要花费 分钟来收集,其价值为 。 小红的总探险时间不能超过 分钟。此外,如果某件宝藏的收集时间 严格大于 分钟,该宝藏将被视为“重型宝藏”。小红在本次探险中收集的“重型宝藏”总数不得超过 个。 每件宝藏最多只能收集一次。请你帮小红计算,在满足时间和重型宝藏数量限制的前提下,她能获得的最大价值总和。
输入描述:
第一行包含三个整数 (),分别表示宝藏总数、最大允许总时间、以及最大允许的重型宝藏数量。接下来的 行,每行包含两个整数 和 (),分别表示第 件宝藏的收集时间与价值。
输出描述:
输出一个整数,表示小红能获得的最大总价值。
示例1
输入
4 100 1
20 50
35 60
25 30
40 70
说明
在样例中,

。宝藏详情如下:
- 宝藏 1:耗时 20,价值 50(普通)
- 宝藏 2:耗时 35,价值 60(重型,因为 35 > 30)
- 宝藏 3:耗时 25,价值 30(普通)
- 宝藏 4:耗时 40,价值 70(重型,因为 40 > 30)
小红可以选择收集宝藏 1、宝藏 3 和 宝藏 4。
总耗时:

。
重型宝藏数量:仅宝藏 4 一件,数量为

。
总价值:

。
可以证明这是满足条件的最大价值方案。
加载中...