Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i-й матч начинается в момент времени l
i и заканчивается в момент времени r
i.
Василиса хочет посмотреть
как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени r
i, то она может после него посмотреть любой матч j, который начинается
не раньше момента времени r
i, то есть l
j > r
i (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы t
между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча i и j, которые просмотрит Василиса, удовлетворяющие условию l
j - r
i => t. Перерыв не может быть до или после всех просмотренных игр.
Помогите Василисе составить набор, содержащий максимальное количество матчей, которые она сможет просмотреть полностью и при этом сделать перерыв продолжительностью не менее t между какими-то матчами, или определите, что такого набора не существует.
Формат входных данных
Первая строка входных данных содержит число n (2 ≤ n ≤ 100 000) - количество показываемых матчей.
Вторая строка входных данных содержит число t (1 ≤ n ≤ 10
9) - минимальная длина перерыва, который должна сделать Василиса.
В следующих n строках содержится по два числа l
i и r
i ( 1 ≤ l
i < r
i ≤ 10
9) - начало и конец i-го матча.
Формат выходных данных
Программа должна вывести число m - максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите m чисел через пробел - номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы t, то выведите число -1.
Замечание
В первом примере ответом будет последовательность матчей 6, 3, 5. Василиса сначала посмотрит матч 6,
который заканчивается в момент времени 4, потом переключится на матч 3, который продолжается с 4 до 6.
Затем она сделает перерыв с 6 по 10, после чего просмотрит матч номер 5 с 10 до 12. Получилось расписание из 3 матчей с перерывом, продолжительность которого равна 4. Заметим, что в данном примере правильным ответом также будет последовательность матчей 6, 4, 5, в этом случае продолжительность перерыва между матчами 4 и 5 будет равна 3.
Во втором примере всего два матча, первый заканчивается в 5, а второй начинается в 9, то есть составить расписание, в котором был бы перерыв продолжительностью не менее t=5, нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
8 13
1 5
4 6
4 7
10 12
2 4
|
3
6 3 5
|
|
2
|
2
5
1 5
9 13
|
-1
|