Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

This round has an unusual addition to the rules. For each problem you must use distinct language. Thus, if you have a submission that has passed at least one test or is being tested at the moment, then for this task you can use only this language and can not use it for other tasks. More details can be read by the link. Different implementations of the same language are considered to be the same language (for example, in C++ you can only solve one problem, regardless of the exact chosen compiler).

No tags yet

No tag edit access

F. Mobile Communications

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA sum of *p* rubles is charged from Arkady's mobile phone account every day in the morning. Among the following *m* days, there are *n* days when Arkady will top up the account: in the day *d*_{i} he will deposit *t*_{i} rubles on his mobile phone account. Arkady will always top up the account before the daily payment will be done. There will be no other payments nor tops up in the following *m* days.

Determine the number of days starting from the 1-st to the *m*-th such that the account will have a negative amount on it after the daily payment (i. e. in evening). Initially the account's balance is zero rubles.

Input

The first line contains three integers *n*, *p* and *m* (1 ≤ *n* ≤ 100 000, 1 ≤ *p* ≤ 10^{9}, 1 ≤ *m* ≤ 10^{9}, *n* ≤ *m*) — the number of days Arkady will top up the account, the amount of the daily payment, and the number of days you should check.

The *i*-th of the following *n* lines contains two integers *d*_{i} and *t*_{i} (1 ≤ *d*_{i} ≤ *m*, 1 ≤ *t*_{i} ≤ 10^{9}) — the index of the day when Arkady will make the *i*-th top up, and the amount he will deposit on this day. It is guaranteed that the indices of the days are distinct and are given in increasing order, i. e. *d*_{i} > *d*_{i - 1} for all *i* from 2 to *n*.

Output

Print the number of days from the 1-st to the *m*-th such that the account will have a negative amount on it after the daily payment.

Examples

Input

3 6 7

2 13

4 20

7 9

Output

3

Input

5 4 100

10 70

15 76

21 12

30 100

67 85

Output

26

Note

In the first example the balance will change as following (remember, initially the balance is zero):

- in the first day 6 rubles will be charged, the balance in the evening will be equal to - 6;
- in the second day Arkady will deposit 13 rubles, then 6 rubles will be charged, the balance in the evening will be equal to 1;
- in the third day 6 rubles will be charged, the balance in the evening will be equal to - 5;
- in the fourth day Arkady will deposit 20 rubles, then 6 rubles will be charged, the balance in the evening will be equal to 9;
- in the fifth day 6 rubles will be charged, the balance in the evening will be equal to 3;
- in the sixth day 6 rubles will be charged, the balance in the evening will be equal to - 3;
- in the seventh day Arkady will deposit 9 rubles, then 6 rubles will be charged, the balance in the evening will be equal to 0.

Thus, in the end of the first, third and sixth days the balance will be negative in the end of the day.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/19/2018 07:33:15 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|