Ett företag testar en teknik för att framställa antimateria som används som bränsle i ett interplanetärt rymdskepp. Antimaterian framställs genom särskilda experiment i en reaktor.

Det finns $n$ kända typer av experiment som ger antimateria. När ett experiment av typ $i$ utförs tillförs mellan $l_i$ och $r_i$ gram antimateria till reaktorns utgående behållare. Av säkerhetsskäl får behållaren inte innehålla mer än $a$ gram antimateria.

Kostnaden för ett experiment av typ $i$ är $c_i$, och värdet av ett gram framställd antimateria är $10^9$.

Om behållaren efter experimenten innehåller $t$ gram antimateria och den sammanlagda kostnaden för experimenten i reaktorn är $s$, beräknas vinsten som $(t\cdot 10^9-s)$. Företaget behöver utveckla en strategi för experimenten som maximerar den vinst som kan garanteras.

Utifrån resultaten av tidigare experiment bestämmer strategin vilken typ av experiment som ska utföras, eller beslutar att inga fler experiment ska utföras. Strategin garanterar vinsten $x$ om, oavsett experimentens resultat, behållaren för det första innehåller högst $a$ gram antimateria och vinsten för det andra blir minst $x$.

Anta till exempel att det bara finns en typ av experiment, som ger mellan $4$ och $6$ gram antimateria, att kostnaden är $10$ och att behållarens kapacitet är $17$ gram. Efter två experiment kan behållaren då innehålla mellan $8$ och $12$ gram antimateria. Om resultatet är $12$ gram får experimentet inte utföras igen, eftersom behållaren kan bli överfull om det ger $6$ gram. I övriga fall kan experimentet utföras en tredje gång, så att behållaren innehåller mellan $12$ och $17$ gram antimateria. I värsta fall måste experimentet utföras tre gånger, till en sammanlagd kostnad av $30$, och vinsten blir $(12\cdot 10^9-30)=11\,999\,999\,970$.

Skriv ett program som bestämmer den största vinst $x$ som kan garanteras.

Indata

Den första raden innehåller två heltal: $n$, antalet typer av experiment, och $a$, den största tillåtna mängden antimateria i behållaren ($1\le n\le 100$, $1\le a\le 2\,000\,000$).

De följande $n$ raderna innehåller vardera tre heltal $l_i$, $r_i$ och $c_i$: den minsta respektive största mängden antimateria som ett experiment av typ $i$ ger, och kostnaden för denna typ av experiment ($1\le l_i\le r_i\le a$, $1\le c_i\le 100$).

Utdata

Utdata ska innehålla ett heltal: den största vinst $x$ som kan garanteras.

Exempel

Indata 1

1 17
4 6 10

Utdata 1

11999999970

Indata 2

2 11
2 2 100
3 5 5

Utdata 2

9999999890

Deluppgifter