|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1555. Lecture
|
| View Problem Statistics | Submit | Problem added debug |
|
Образование — это то, что остаётся, когда забываешь всё, чему учился в школе. Эйнштейн Константин Игоревич читает завтра лекцию по алгебре. Сегодня же ему надо решить, какие из теорем, которые он будет рассказывать, следует доказать. С одной стороны, лекция не может длиться более T минут, так что на доказательство вообще всех теорем времени, скорее всего, не хватит. С другой стороны, хочется, чтобы лекция оказалась для студентов как можно полезнее. Полезность лекции определяется как сумма полезностей всех доказанных теорем, в то время как полезность теоремы — какое-то заранее известное для каждой теоремы число. Теоремы делятся на три класса по сложности, и их доказательство занимает одну, две или три минуты в зависимости от класса. Конечно же, прилежные студенты заранее выучили все определения и формулировки, так что всё время лекции можно потратить на доказательство теорем. Входные данные В первой строке входного файла заданы через пробел два числа N и T (1≤N≤100000, 1≤T≤300000) — количество теорем и продолжительность лекции (в минутах). Далее идут N строк, в каждой два числа ti и ai (1≤ti≤3, 0≤ai≤109), обозначающих класс сложности i-й теоремы (то есть, время в минутах, требуемое на её доказательство) и её полезность. Выходные данные Выведите одно число — максимальную полезность завтрашней лекции Константина Игоревича. Примеры Входные данные 3 3 Выходные данные 17 Входные данные 3 4 Выходные данные 15
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Trainings in Perm 2009 / | 06.07.09 Big Contest / |
| 1554. C - Jack Joker | 1555. | 1556. E - Soldiers Suicide | 1557. F - Squaring the Circle | 1558. G - Timetable |
| time generating 0.11 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |