Задача №115180. Вечер кёрлинга
Сегодня вечером по телевизору на разных каналах будут показывать \(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 < r_i \le 10^9\)) — начало и конец \(i\)-го матча.
Программа должна вывести число \(m\) — максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите \(m\) чисел через пробел — номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы \(t\), то выведите число \(-1\).
Решения, верно работающие при \(n \le 15\), будут оцениваться в \(20\) баллов.
Решения, верно работающие при \(n \le 1000\), будут оцениваться в \(40\) баллов.
Решения, верно работающие при \(r_i \le 10^5\), будут оцениваться в \(30\) баллов.
В первом примере ответом будет последовательность матчей \(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\), нельзя.
6 3 8 13 1 5 4 6 4 7 10 12 2 4
3 6 3 5
2 5 1 5 9 13
-1