每天早上都会从阿尔卡季的手机账户中扣除一笔卢布的费用。在接下来的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。
因此,在第一天、第三天和第六天结束时,余额最终将为负值。