E. Поход
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Путешественник планирует водный поход по реке. Он отметил пригодные для ночлега места и выписал расстояния до них от своего старта. Каждое из таких мест дополнительно характеризуется своей живописностью, так для i-го места для стоянки расстояние от старта равно xi, а живописность равна bi. Путешественник будет двигаться по реке в одном направлении, можно считать, что он стартует из точки 0 на координатной прямой, а места ночлега — это точки с координатами xi.

Каждый день путешественник хочет проходить расстояние l. На практике же оказывается, что это не всегда возможно, ведь заканчивать путь каждый день ему необходимо в одном из мест для ночлега. Кроме того, в путешественнике борются два желания: каждый день проходить расстояние l и посетить наиболее живописные места.

Будем считать, что если за сутки путешественник проходит расстояние rj, то он испытывает недовольство , а его суммарное недовольство за поход вычисляется как суммарное недовольство по всем дням.

Помогите спланировать путь таким образом, чтобы минимизировать относительное суммарное недовольство: суммарное недовольство поделенное на суммарную живописность всех использованных мест ночлега.

Маршрут путешественника обязательно должен заканчиваться в самом дальнем месте ночлега.

Входные данные

В первой строке входных данных записаны целые числа n, l (1 ≤ n ≤ 1000, 1 ≤ l ≤ 105) — количество мест для ночлега и оптимальная длина пути за одни сутки.

Далее следует n строк, каждая строка описывает одно место для ночлега парой целых чисел xi, bi (1 ≤ xi, bi ≤ 106). Никакие два места для ночлега не имеют одинаковые xi, строки заданы в порядке строго возрастания xi.

Выходные данные

Выведите маршрут путешественника в виде последовательности номеров использованных мест ночлега в порядке их прохождения. Места нумеруйте от 1 до n в порядке возрастания xi. Последнее выведенное число обязательно должно быть равно n.

Примеры
Входные данные
5 9
10 10
20 10
30 1
31 5
40 10
Выходные данные
1 2 4 5 
Примечание

В тесте из примера минимальное значение относительного суммарного недовольства примерно равно 0.097549. Это значение может быть вычислено как .