Сегодня вечером по телевизору на разных каналах будут показывать $$$n$$$ матчей по кёрлингу, причём $$$i$$$-й матч начинается в момент времени $$$l_i$$$ и заканчивается в момент времени $$$r_i$$$.
Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени $$$r_i$$$, то она может после него посмотреть любой матч $$$j$$$, который начинается не раньше момента времени $$$r_i$$$, то есть $$$l_j\ge r_i$$$ (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы $$$t$$$ между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча $$$i$$$ и $$$j$$$, которые просмотрит Василиса, удовлетворяющие условию $$$l_j-r_i\ge t$$$. Перерыв не может быть до или после всех просмотренных игр.
Помогите Василисе составить набор, содержащий максимальное количество матчей, которые она сможет просмотреть полностью и при этом сделать перерыв продолжительностью не менее $$$t$$$ между какими-то матчами, или определите, что такого набора не существует.
Первая строка входных данных содержит число $$$n$$$ ($$$2 \le n \le 100\,000$$$) — количество показываемых матчей.
Вторая строка входных данных содержит число $$$t$$$ ($$$1 \le t \le 10^9$$$) — минимальная длина перерыва, который должна сделать Василиса.
В следующих $$$n$$$ строках содержится по два числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \lt r_i \le 10^9$$$) — начало и конец $$$i$$$-го матча.
Программа должна вывести число $$$m$$$ — максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите $$$m$$$ чисел через пробел — номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы $$$t$$$, то выведите число $$$-1$$$.
Решения, верно работающие при $$$n \le 15$$$, будут оцениваться в $$$20$$$ баллов.
Решения, верно работающие при $$$n \le 1000$$$, будут оцениваться в $$$40$$$ баллов.
Решения, верно работающие при $$$r_i \le 10^5$$$, будут оцениваться в $$$30$$$ баллов.
638 131 54 64 710 122 4
3 6 3 5
251 59 13
-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$$$, нельзя.
