← 返回题目列表

Codeforces · 926/F

F. 移动通信

中文机器翻译题面 查看原题

每天早上都会从阿尔卡季的手机账户中扣除一笔卢布的费用。在接下来的m天内,有n天Arkady会向账户充值:在第di天他将向他的手机账户存入ti个卢布。 Arkady 始终会在每日付款完成之前为帐户充值。接下来的 m 天内不会有其他付款或充值。

确定从第 1 天到第 m 天的天数,以便帐户在每日付款后(即晚上)出现负金额。最初账户余额为零卢布。

输入

第一行包含三个整数 n、p 和 m (1 ≤ n ≤ 100 000, 1 ≤ p ≤ 109, 1 ≤ m ≤ 109, n ≤ m) — Arkady 为帐户充值的天数、每日付款的金额以及您应该检查的天数。

接下来 n 行的第 i 行包含两个整数 di 和 ti (1 ≤ di ≤ m, 1 ≤ ti ≤ 109) — Arkady 将进行第 i 次充值的日期的索引,以及他在这一天将存入的金额。保证日期的索引是不同的并且按升序给出,即。 e.对于从 2 到 n 的所有 i,di > di - 1。

输出

打印从第 1 到第 m 的天数,以便在每日付款后帐户上的金额为负数。

示例

输入 #1

3 6 7
2 13
4 20
7 9

输出 #1

3

输入 #2

5 4 100
10 70
15 76
21 12
30 100
67 85

输出 #2

26

注意

在第一个示例中,余额将更改如下(请记住,最初余额为零):

1. 第一天收取6卢布,晚上余额等于 - 6;
2. 第二天阿尔卡季存入13卢布,然后收取6卢布,晚上余额等于1;
3、第三天收取6卢布,晚上余额等于 - 5;
4.第四天阿尔卡季存入20卢布,然后收取6卢布,晚上余额等于9;
5、第五天收取6卢布,晚上余额等于3;
6、第六天收取6卢布,晚上余额等于 - 3;
7. 第七天阿尔卡季将存入9卢布,然后收取6卢布,晚上余额将等于0。

因此,在第一天、第三天和第六天结束时,余额最终将为负值。