Задача G. Гонка со временем ≡

Условие

Директор школы "Лицей Программистов" города Линейска сумел привить ученикам этой школы хорошую дисциплину, но, несмотря на это, многие ученики продолжают опаздывать на уроки.

В Линейске есть всего одна главная улица, на которой расположен и сам лицей, и живут все его ученики. Дисциплинированные школьники выходят из своих домов в одно и то же время. Но, к сожалению, все они живут на разном расстоянии от школы и добираются с разной, но постоянной скоростью (среди учеников есть как весьма неторопливые, так и будущая чемпионка мира по бегу на 100 метров Маша Гайка).

Для улучшения ситуации с опозданиями школа купила один веломобиль, который взялся водить сторож школы. Веломобиль способен помимо водителя перевозить одного школьника. Веломобиль перемещается с постоянной скоростью v.

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

Директор хочет начинать занятия как можно раньше, но для этого нужно, чтобы все ученики добрались до лицея. Он поручил вам помочь составить план, по которому должен действовать водитель веломобиля, чтобы время прибытия последнего школьника в школу было минимальным.

Формат входного файла

Первая строка входного файла содержит два целых числа n, v (1 ≤ n ≤ 10⁵, 1 ≤ v ≤ 1000) — соответственно количество людей и скорость веломобиля. Следующие n строк содержат по два целых числа x_i, v_i (1 ≤ x_i, v_i ≤ 1000) — расстояния от школы до дома i-ого ученика и его скорость.

Формат выходного файла

В первую строку выходного файла выведите вещественное число t — минимальное время, за которое все школьники доберутся до лицея. Во второй строке выходного файла выведите единственное число k — количество учеников, которых нужно подвезти. В следующих k строках выведите по два числа — номер школьника, которого нужно подвезти, и расстояние от школы, на котором этот школьник должен сесть в веломобиль.

Школьников нужно выводить в том же порядке, в котором они будут ехать на веломобиле.

Выводите все вещественные числа как можно точнее. При проверке вашего решения при сравнении вещественных чисел будет допускаться абсолютная или относительная погрешность 10⁻⁶.

Примеры тестов

5 4
1 1
4 2
3 1
7 5
5 1

2.4
2
5 4
3 0.8