Антивещество

시간 제한2초메모리 제한128 MB

요약

용기 용량 a를 넘지 않는 선에서 실험을 골라, 최악의 경우에도 보장되는 이익 t*10^9 - s의 최댓값을 구한다.} output only JSON. Wait I must output JSON only. Let me produce proper JSON with summaryKo up to 600 chars. The schema requires summaryKo minLength 1 maxLength 600. Also note

난이도: 보통10점 중 7점
유형: 동적 계획법, 게임 이론, 그리디
정답자: 아직 제출이 없습니다

문제

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

Известно $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$ , которую гарантированно можно получить.

예제2

예제 1
입력
```
1 17
4 6 10
```
예상 출력
```
11999999970
```
예제 2
입력
```
2 11
2 2 100
3 5 5
```
예상 출력
```
9999999890
```