20468번 - Антивещество 서브태스크다국어

Компания тестирует технологию получения антивещества, используемого в качестве топлива в межпланетном звездолёте. Антивещество получается в результате специальных экспериментов в реакторе. 

Известно $n$ типов экспериментов, приводящих к получению антивещества. В результате проведения эксперимента $i$-го типа в выходной контейнер реактора добавляется от $l_i$ до $r_i$ граммов антивещества. Из соображений безопасности запрещается накапливать в контейнере более $a$ граммов антивещества.

Затраты на проведение эксперимента $i$-го типа составляют $c_i$, а стоимость одного грамма полученного антивещества составляет $10^9$. 

Если после проведения экспериментов в контейнере образовалось $t$ граммов антивещества, а суммарные затраты на проведение экспериментов в реакторе составили $s$, то прибыль определяется по формуле ($t \cdot 10^9 - s$). Компании необходимо разработать стратегию проведения экспериментов, позволяющую максимизировать прибыль, которую можно гарантированно получить. 

В зависимости от результатов предыдущих экспериментов стратегия определяет, эксперимент какого типа следует провести, или решает прекратить дальнейшее выполнение экспериментов. Стратегия позволяет гарантированно получить прибыль $x$, если при любых результатах проведения экспериментов: во-первых, в контейнере реактора оказывается не более $a$ граммов антивещества, во-вторых, прибыль составит не менее $x$.

Например, пусть возможен только один тип эксперимента, порождающий от 4 до 6 граммов антивещества, затраты на его проведение равны 10, а вместимость контейнера составляет 17 граммов. Тогда после двукратного проведения эксперимента в контейнере может оказаться от 8 до 12 граммов антивещества. Если получилось 12 граммов, то больше проводить эксперимент нельзя, так как в случае получения 6 граммов антивещества контейнер может переполниться. В остальных случаях можно провести эксперимент в третий раз и получить от 12 до 17 граммов антивещества. В худшем случае придётся провести эксперимент трижды, затратив в сумме 30, прибыль составит $(12\cdot 10^9-30)=11\,999\,999\,970$.

Требуется написать программу, которая определяет максимальную прибыль $x$, которую гарантированно можно получить.

Первая строка входных данных содержит два целых числа: $n$ --- количество типов экспериментов и $a$ --- максимально допустимое количество антивещества в контейнере ($1 \leq n \le 100$, $1 \leq a \leq 2\cdot 10^6$).

Следующие $n$ строк содержат по три целых числа $l_i$, $r_i$ и $c_i$ --- минимальное и максимальное количество антивещества, получаемое в результате эксперимента типа $i$, и затраты на эксперимент этого типа, соответственно ($1 \leq l_i \leq r_i \leq a$, $1 \leq c_i \leq 100$).  

Выходные данные должны содержать одно целое число --- максимальную прибыль $x$, которую гарантированно можно получить.