Автобус
(Время: 1 сек. Память: 16 Мб Сложность: 39%)
Василий работает водителем автобуса, и у него есть по-настоящему тяжелая работа: он перевозит пассажиров из пункта A в пункт B. При этом он должен выполнять свою работу безопасно и как можно быстрее. Кроме того, каждый водитель должен повиноваться дорожным правилам и нормам, иначе, он будет оштрафован местной полицией.
Маршрут Василия состоит из N отрезков, которые он проезжает последовательно, начиная от 1-го и завершая N-м отрезком. У каждого отрезка задана длина в километрах Di.
Конечно, на маршруте Василия есть ограничения скорости. У каждого отрезка есть свое собственное ограничение скорости Li км/ч. В случае превышения скорости на i-м отрезке, водитель автобуса будет немедленно остановлен полицейским, который потратит Hi часов на заполнение соответствующих бумаг. Водитель не может быть остановлен более одного раза на каждом отрезке.
Автобус едет вдоль маршрута с постоянной скоростью S, которую Василий выбирает в начале маршрута (в пункте A). Автобус не может превышать максимальную конструктивную скорость, которая определена значением M км/ч.
Пожалуйста, помогите Василию выбирать правильную скорость, чтобы достигнуть конечного пункта B как можно быстрее.
Входные данные
Первая строка входного файла INPUT.TXT содержит два числа, разделенные пробелом: количество отрезков N (N ≤ 1000) в маршруте Василия и максимально возможную конструктивную скорость автобуса M (M ≤ 105). Далее идут N строк, в каждой из которых определены разделенные пробелом значения Di, Li и Hi, описывающие i-й отрезок пути (Di, Hi ≤ 1000, Li ≤ 105). Все числа, определенные во входных данных натуральные.
Выходные данные
В выходной файл OUTPUT.TXT выведите оптимальную скорость автобуса. В случае неоднозначного ответа следует выбрать наибольшее значение.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 100
1000 100 10 | 100 |
Пояснение к примеру
Здесь у нас простой случай, когда максимальная скорость 100 км/ч является оптимальной для единственного отрезка пути. Таким образом, Василий может выбрать эту скорость и закончить свой маршрут через 10 часов. Поэтому ответ: 100.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
