Un'azienda sta sperimentando una tecnologia per produrre antimateria, utilizzata come combustibile in un'astronave interplanetaria. L'antimateria viene ottenuta mediante speciali esperimenti in un reattore.

Sono noti $n$ tipi di esperimenti che producono antimateria. Un esperimento di tipo $i$ aggiunge al contenitore di uscita del reattore da $l_i$ a $r_i$ grammi di antimateria. Per motivi di sicurezza è vietato accumulare nel contenitore più di $a$ grammi di antimateria.

Il costo di un esperimento di tipo $i$ è $c_i$, mentre il valore di un grammo di antimateria prodotta è $10^9$.

Se dopo gli esperimenti nel contenitore si trovano $t$ grammi di antimateria e il costo complessivo degli esperimenti nel reattore è $s$, il profitto è dato dalla formula $(t\cdot 10^9-s)$. L'azienda deve elaborare una strategia di esecuzione degli esperimenti che massimizzi il profitto ottenibile con certezza.

A seconda dei risultati degli esperimenti precedenti, la strategia determina quale tipo di esperimento eseguire oppure decide di interrompere gli esperimenti. Una strategia permette di ottenere con certezza un profitto $x$ se, per qualsiasi risultato degli esperimenti, innanzitutto nel contenitore del reattore si trovano al massimo $a$ grammi di antimateria e, in secondo luogo, il profitto è almeno $x$.

Ad esempio, supponiamo che sia disponibile un solo tipo di esperimento, che produce da $4$ a $6$ grammi di antimateria, che il suo costo sia $10$ e che la capacità del contenitore sia $17$ grammi. Dopo due esperimenti, il contenitore può contenere da $8$ a $12$ grammi di antimateria. Se sono stati ottenuti $12$ grammi, non si possono eseguire altri esperimenti, perché producendo $6$ grammi il contenitore potrebbe traboccare. Negli altri casi si può eseguire l'esperimento una terza volta e ottenere da $12$ a $17$ grammi di antimateria. Nel caso peggiore bisognerà eseguire tre esperimenti, con un costo complessivo di $30$, e il profitto sarà $(12\cdot 10^9-30)=11\,999\,999\,970$.

Scrivete un programma che determini il massimo profitto $x$ ottenibile con certezza.

Input

La prima riga dell'input contiene due interi: $n$, il numero di tipi di esperimenti, e $a$, la quantità massima consentita di antimateria nel contenitore ($1\le n\le 100$, $1\le a\le 2\,000\,000$).

Le successive $n$ righe contengono ciascuna tre interi $l_i$, $r_i$ e $c_i$: rispettivamente la quantità minima e massima di antimateria prodotta da un esperimento di tipo $i$ e il costo di un esperimento di quel tipo ($1\le l_i\le r_i\le a$, $1\le c_i\le 100$).

Output

L'output deve contenere un solo intero: il massimo profitto $x$ ottenibile con certezza.

Esempi

Input 1

1 17
4 6 10

Output 1

11999999970

Input 2

2 11
2 2 100
3 5 5

Output 2

9999999890

Sottoproblemi