@RomanZemin

Обнимание панды
Первая девушка
— А вот в китайских зоопарках есть такая работа — обнимать панд.
Вторая девушка (мечтательно)
— Вот бы такую работу! Целыми днями можно только спать, селфиться и обнимать панду.
Подслушано в общественном транспорте.

Одна девушка получила работу своей мечты — обнимать панду. Общая продолжительность контракта на работу составляет s минут. Мы предполагаем, что контракт начинается в момент времени 0 и завершается в момент времени s. Работодатель составил ей рабочий график — интервалы времени, в течение которых она должна обнимать панду. Каждый интервал задается двумя целыми числами ai и bi. Девушка начинает обнимать панду ровно в момент ai и заканчивает в момент bi. Теперь девушке надо составить график, по которому она будет делать селфи. Девушка хочет, чтобы интервал между селфи не превышал t минут, чтобы никто не подумал, что она умерла. Вместе с тем, она хочет, чтобы общее количество селфи было как можно меньшим, чтобы никто не подумал, что она дурочка, которая может только спать, селфиться и обнимать панду. При этом, строго запрещено делать селфи во время работы, поскольку панда не давала свое разрешение на фотографирование, однако, не возбраняется делать селфи в момент начала смены и в момент конца смены. После большой тренировки девушка научилась делать селфи и выкладывать его очень быстро, поэтому, мы считаем, что это происходит мгновенно. Помогите девушке составить график для селфи на время контракта так, чтобы количество селфи было минимальным с учетом указанных требований. Первое селфи обязательно делается в момент времени 0, последнее — в момент времени s.

Input format
В первой строке через пробел записаны три натуральных числа n, t и s — количество рабочих смен, максимальный интервал между селфи и общая продолжительность контракта на работу. Далее в n строках заданы по два целых неотрицательных числа ai и bi — начало и конец каждой рабочей смены. Рабочие смены не пересекаются, каждая следующая смена начинается строго после окончания предыдущей, время окончания смены строго больше ее начала. Время окончания последней смены не превышает s. При этом n≤200000, s,t≤ 1018. Гарантируется, что bi-ai ≤ t

Output format
Вывести одно число — количество селфи в графике.

Examples
Input Output
2 20 40
0 15
20 40
3
3 20 50
1 2
5 25
30 50
5
Notes
В первом тестовом примере девушка может делать селфи в моменты времени 0, 20 и 40.

Во втором тестовом примере девушка может делать селфи в моменты 0,5,25,30,50

Методика проверки
При тестировании задачи выделяются следующие тестовые случаи.

s≤1000 (40 баллов)
s≤106,n≤200000 (20 баллов)
s≤1018,n≤200000, s/t≤106 (20 баллов)
Без ограничений к условию задачи. (20 баллов).

0