Дорожные пробки
Самая неприятная вещь в пробках в Москве заключается в том, что водители постоянно пытаются внезапно поменять полосу движения, чтобы двигаться быстрее. В этой задаче Вам следует выяснить, является ли такое поведениеразумной стратегией или нет.
Мы изучим относительно простую математическую модель дорожного затора. Предположим, что имеющаяся дорога состоит из n полос, пронумерованных от 1 до n, на i-ой полосе движение происходит со скоростью b[i] + a[i] * sin(t + delta[i]) в момент времени t. Известно, что неравенство b[i] > a[i] всегда имеет место, то есть скорость движения всегда положительна. Вы можете сменить полосу движения в любой момент времени, причем c * |x - y| времени займет смена полосы x на полосу y. Мы предполагаем, что Вы не продвигаетесь вперед в течение этого периода.
Определите время, за которое Вы преодолеете расстояние d, а также способ достижения этого времени. Вы стартуете в момент времени 0 на полосе 1, финишировать Вы можете на любой полосе.
Входные данные
Первая строка содержит два целых числа n и d, а также действительное число c (1 ≤ n ≤ 5, 1 ≤ d ≤ 1000, 0.001 ≤ c ≤ 1000). Следующие n строк описывают полосы, каждая из которых содержит два целых числа a[i] и b[i] и действительное число delta[i] (0 ≤ a[i] < b[i] ≤ 100, 0 ≤ delta[i] < 2 * pi).
Выходные данные
В первой строке выведите минимальное время, необходимое для перемещения на расстояние d. Во второй строке выведите количество k изменений полосы движения, необходимых для этого. Значение k не должно быть больше 10^6. Гарантируется, что всегда существует оптимальная стратегия, требующая не более 10^6 изменений полос движения. В следующих k строках выведите сами изменения: каждая строка должна содержать новый номер полосы и время начала изменения. Изменения должны выводиться в хронологическом порядке. Если имеется несколько возможных решений, то выведите любой.
Числа с плавающей точкой следует выводить с максимальной точностью. Ваше решение будет считаться правильным, если проверка вашего расписания не приведет к несоответствиям более чем на 10^(-6) (при проверке пройденного расстояния, при проверке того, что изменения полосы движения не перекрываются и так далее). Поэтому Вам лучше вывести не менее 10 - 12 десятичных знаков в каждом действительном числе.