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

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


 

Метрострой

(Время: 1 сек. Память: 32 Мб Сложность: 22%)

Буровая установка «Мегабур 2022» для прокладки туннелей метро Байтсбурга имеет n двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение x.

У каждого двигателя есть два режима, если на него подается напряжение x, то i-й двигатель работает в первом режиме, если x ≤ zi и во втором режиме, если x > zi.

При этом i-й двигатель характеризуется удельной мощностью ai в первом режиме и bi во втором режиме. Это означает, что увеличение напряжения на 1 когда двигатель находится в первом режиме, приводит к увеличению его мощности на ai, а во втором режиме приводит к увеличению его мощности на bi. Иначе говоря, при подаче напряжения x, если i-й двигатель находится в первом режиме он работает с мощностью aix, а если во втором режиме, то с мощностью aizi + bi(x - zi).

Для прокладки туннеля суммарная мощность двигателей должна быть не меньше p. Какое минимальное целочисленное напряжение необходимо подать на установку, чтобы суммарная мощность двигателей была больше или равна p?

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и p (1 ≤ n ≤ 100; 1 ≤ p ≤ 1012). Следующие n строк описывают двигатели и содержат по три целых числа zi, ai, bi (1 ≤ zi ≤ 109; 1 ≤ ai, bi ≤ 104).

Выходные данные

В выходной файл OUTPUT.TXT требуется вывести одно целое число – минимальное напряжение, которое необходимо подать на установку.

Примеры

INPUT.TXTOUTPUT.TXT
11 6
4 1 2
5
23 15
2 3 3
4 2 1
5 2 2
3

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


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Разделение прямоугольника
 B. Произведение Фибоначчи
 C. Робот-пылесос
 D. Разноцветные точки
 E. Метрострой
 F. Красивые последовательности
 G. Камни
 H. Обыкновенная задача про строки

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



горелка mapp