Космическая связь
В этой задаче от вас потребуется написать программу для составления расписания сеансов связи со спутником. Каждый сеанс заключается в обмене короткими сообщениями, поэтому мы считаем, что он происходит мгновенно. Поскольку ресурсы оборудования ограничены, следует стремиться к минимизации количества сеансов. Вместе с тем, интервал времени между сеансами не должен превышать dd миллисекунд. Кроме того, существуют промежутки времени, в течении которых связь невозможна. При этом на границах промежутка мгновенный сеанс связи возможен. Расписание составляется на ttмиллисекунд. Первый сеанс должен обязательно состояться в момент 00, а последний — в момент tt.
Рассмотрим пример. Пусть t=100t=100, d=20d=20 и задано 3 промежутка недоступности связи: (5;25), (27;40), (75;90)(5;25),(27;40),(75;90). Тогда потребуется восемь сеансов связи, которые можно провести в моменты времени 0, 5, 25,45, 65, 75,90,1000,5,25,45,65,75,90,100. Конкретное расписание может быть другим, но в любом случае количество сеансов не может быть меньше восьми.
Ваша программа должна по имеющейся информации найти минимальное возможное количество сеансов связи.
Формат входных данных
В первой строке через пробел записаны три натуральных числа nn, dd и tt — количество интервалов недоступности связи, максимальный интервал между между сеансами и время, на которое составляется расписание. nleq 200000n≤200000, d,tleq 10^{9}d,t≤10
9
. Далее в nn строках заданы по два целых неотрицательных числа a_ia
i
и b_ib
i
— начало и конец каждого интервала недоступности связи. b_i-a_ileq db
i
−a
i
≤d. Интервалы недоступности связи не пересекаются, каждый следующий интервал начинается строго после окончания предыдущего. 0leq a_1
1
1
2
2
<…
n
n
≤t.
Формат выходных данных
Вывести одно число — количество сеансов связи в графике.
Методика проверки
Программа проверяется на 25 тестах. Прохождение каждого теста оценивается в 0.8 балла. Тест из условия задачи при проверке не используется.
В первых десяти тестах tleq 1000t≤1000. В следующих 10 тестах tleq 10^6t≤10
6
.
Sample Input:
3 20 100
5 25
27 40
75 90
Sample Output:
8
Пусть s — расстояние. s/A скорость Первого, s/B Второго, совместная скорость сближения (s/A+s/B)=s(A+B)/A*B, тогда время=путь/скорость = s/[s(A+B)/A*B]= A*B/(A+B), мин -ответ