← 返回比赛
已结束 GESP马上AK赛
← 上一题 下一题 →

A7203 | 年夜牌局

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

除夕夜的牌局里，你的生命值只剩 $H$，对手甩出一句：

你的血量已经风中残烛……


但新年也有新运气。牌局共 $n$ 回合，第 $i$ 回合依次发生两件事：

1. 你抽到一张“红包牌”，面值为 $c_i$，加入手牌（可以留到以后再用）。
2. 随后对手造成 $d_i$ 点伤害（$d_i\ge 0$）。

在每回合伤害结算之前，你可以从手牌中打出若干张红包牌（每张只能用一次），每打出一张就使生命值增加对应面值。
但整场牌局里，你最多只能打出 $k$ 张红包牌。

只要某回合伤害结算后你的生命值 $\le 0$，你立刻倒下，牌局结束。

请你输出：在最优策略下，你最多能完整撑过多少回合。

输入格式

第一行三个整数 $n,k,H$。
接下来 $n$ 行，每行两个整数 $c_i,d_i$。

输出格式

输出一个整数，表示最多能撑过的回合数（范围 $0\sim n$）。

输入输出样例

输入 #1
6 3 11
4 6
8 9
3 6
0 1
2 1
0 1
输出 #1
6
输入 #2
4 1 5
10 6
0 6
0 1
0 1
输出 #2
4
C++ 编辑器
输入
输出