Пробка на дороге
Самое раздражающее в московских пробках — это то, что водители постоянно пытаются внезапно перестроиться в другой ряд, чтобы двигаться быстрее. В этой задаче вам предстоит выяснить, является ли это разумной стратегией или нет.
Мы изучим относительно простую математическую модель пробки. Предположим, что есть дорога с N рядами, пронумерованными от 1 до N, и i-й ряд движется со скоростью b_i+a_i·sin(t+δ_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 и число с плавающей точкой δ_i, 0 ≤ a_i < b_i ≤ 100, 0 ≤δ_i < 2π.
Выходные данные
В первой строке выходных данных выведите минимальное время, необходимое для преодоления расстояния d. Во второй строке выведите число K перестроений, необходимых для этого. K не должно превышать 10^6, гарантируется, что всегда существует оптимальная стратегия, требующая не более 10^6 перестроений. В следующих K строках выведите сами перестроения, каждая строка должна содержать номер нового ряда и время, когда начато перестроение. Перестроения должны быть выведены в хронологическом порядке. Если существует несколько возможных расписаний, выведите любое.
Выведите все числа с плавающей точкой с максимальной возможной точностью. Ваше решение будет считаться правильным, если проверка вашего расписания не приведет к расхождениям более чем 10^{-6} (при проверке общего пройденного расстояния, при проверке, что перестроения не пересекаются и т.д.), поэтому лучше выводить не менее 10-12 знаков после запятой в каждом числе с плавающей точкой.