A 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.

Difficulty: HARD

Starter code:

Solutions:
(n, p, m) = map(int, input().split())
lastd = 0
acc = 0
output = 0
neg = 0
for i in range(n):
	(d, t) = map(int, input().split())
	acc += (d - lastd - 1) * -p
	if acc < 0:
		output += acc // -p - neg
		neg = acc // -p
		if acc % p != 0:
			output += 1
			neg += 1
	acc += t - p
	if acc < 0:
		output += 1
		neg = acc // -p
		if acc % p != 0:
			neg += 1
	else:
		neg = 0
	lastd = d
if d < m:
	acc += (m - d) * -p
	if acc < 0:
		output += acc // -p - neg
		if acc % p != 0:
			output += 1
print(output)


rd = lambda : map(int, input().split())
(n, p, m) = rd()
(q, l, r) = (0, 0, 0)
for i in range(n):
	(d, t) = rd()
	c = d - q - 1
	r += max(min(c - l // p, c), 0)
	l -= p * (c + 1) - t
	r += l < 0
	q = d
c = m - q
print(r + max(min(c - l // p, c), 0))


(n, p, m) = map(int, input().split())
(flag, t_neg, t_in, d, tot) = (0, 0, 0, 1, 0)
for i in range(n):
	ini_d = d
	if flag == 1:
		tot += t - p
		if tot < 0:
			t_neg += 1
	(d, t) = map(int, input().split())
	if flag == 0:
		t_neg = d - ini_d
		tot = t_neg * -p
		flag = 1
	else:
		tot += (d - 1 - ini_d) * -p
		if tot < 0:
			if tot <= (d - 1 - ini_d) * -p:
				t_neg += d - 1 - ini_d
			else:
				x = int(-tot % p)
				y = int(-tot / p)
				if x != 0:
					t_neg += y + 1
				else:
					t_neg += y
ini_d = d
tot += t - p
if tot < 0:
	t_neg += 1
tot += (m - ini_d) * -p
if tot < 0:
	if tot <= (m - ini_d) * -p:
		t_neg += m - ini_d
	else:
		x = int(-tot % p)
		y = int(-tot / p)
		if x != 0:
			t_neg += y + 1
		else:
			t_neg += y
print(t_neg)


(n, p, m) = input().split()
n = int(n)
p = int(p)
m = int(m)
ans = 0
curb = 0
curd = 1
for i in range(0, n):
	(tday, tplus) = input().split()
	tday = int(tday)
	tplus = int(tplus)
	if curb < 0:
		ans += tday - curd
		curb -= p * (tday - curd)
	elif curb - p * (tday - curd) < 0:
		curb -= p * (tday - curd)
		x = -curb
		xx = x // p
		if xx * p < x:
			xx += 1
		x = xx
		ans += x
	else:
		curb -= p * (tday - curd)
	curd = tday
	curb += tplus
tday = m + 1
if curb < 0:
	ans += tday - curd
	curb -= p * (tday - curd)
elif curb - p * (tday - curd) < 0:
	curb -= p * (tday - curd)
	x = -curb
	xx = x // p
	if xx * p < x:
		xx += 1
	x = xx
	ans += x
print(ans)