Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Автобус

(Время: 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.TXTOUTPUT.TXT
11 100
1000 100 10
100

Пояснение к примеру

Здесь у нас простой случай, когда максимальная скорость 100 км/ч является оптимальной для единственного отрезка пути. Таким образом, Василий может выбрать эту скорость и закончить свой маршрут через 10 часов. Поэтому ответ: 100.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru