Затор на дорозі
Найбільш дратівливим у московських заторах є те, що водії постійно намагаються раптово змінити смугу руху, щоб рухатися швидше. У цій задачі вам потрібно з'ясувати, чи є така стратегія розумною.
Ми розглянемо відносно просту математичну модель затору. Припустимо, що є дорога з N смугами, пронумерованими від 1 до N, і i-та смуга рухається зі швидкістю b_i+a_i·sin(t+δ_i) у момент часу t. Завжди виконується умова, що b_i > a_i, тобто швидкість руху завжди позитивна. Ви можете змінити смугу в будь-який момент, це займає c·|x-y| часу для переходу з x-ої смуги на y-ту. Припустимо, що під час цього періоду ви не рухаєтеся вперед.
Визначте час, необхідний для подолання відстані d, і метод досягнення цього часу. Ви починаєте в момент 0 на першій смузі, закінчити можна на будь-якій смузі.
Вхідні дані
У першому рядку вхідних даних містяться два цілі числа 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 знаків після коми в кожному числі з плаваючою комою.