Дорожні затори
Найбільш неприємним аспектом заторів у Москві є те, що водії постійно намагаються раптово змінити смугу руху, щоб рухатися швидше. У цьому завданні вам потрібно визначити, чи є така поведінка розумною стратегією.
Ми розглянемо відносно просту математичну модель дорожнього затору. Припустимо, що дорога складається з 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 десяткових знаків у кожному дійсному числі.