Ein Unternehmen erprobt eine Technologie zur Herstellung von Antimaterie, die als Treibstoff für ein interplanetarisches Raumschiff verwendet wird. Die Antimaterie entsteht durch spezielle Experimente in einem Reaktor.

Es sind $n$ Arten von Experimenten bekannt, mit denen Antimaterie erzeugt werden kann. Bei einem Experiment der Art $i$ werden dem Ausgabebehälter des Reaktors zwischen $l_i$ und $r_i$ Gramm Antimaterie hinzugefügt. Aus Sicherheitsgründen dürfen sich im Behälter nicht mehr als $a$ Gramm Antimaterie ansammeln.

Ein Experiment der Art $i$ kostet $c_i$, und ein Gramm der erzeugten Antimaterie hat einen Wert von $10^9$.

Wenn sich nach den Experimenten $t$ Gramm Antimaterie im Behälter befinden und die Gesamtkosten der Experimente im Reaktor $s$ betragen, ist der Gewinn $(t\cdot 10^9-s)$. Das Unternehmen muss eine Strategie zur Durchführung der Experimente entwickeln, die den garantiert erzielbaren Gewinn maximiert.

Abhängig von den Ergebnissen der bisherigen Experimente legt die Strategie fest, welche Art von Experiment als Nächstes durchgeführt wird, oder entscheidet, keine weiteren Experimente durchzuführen. Eine Strategie garantiert einen Gewinn $x$, wenn für alle möglichen Ergebnisse der Experimente erstens nicht mehr als $a$ Gramm Antimaterie im Behälter des Reaktors liegen und zweitens der Gewinn mindestens $x$ beträgt.

Angenommen, es gibt nur eine Art von Experiment, die zwischen $4$ und $6$ Gramm Antimaterie erzeugt. Ihre Kosten betragen $10$, und der Behälter fasst $17$ Gramm. Nach zwei Experimenten können sich dann zwischen $8$ und $12$ Gramm Antimaterie im Behälter befinden. Sind es $12$ Gramm, darf kein weiteres Experiment durchgeführt werden, da der Behälter bei einer Erzeugung von $6$ Gramm Antimaterie überlaufen könnte. In allen anderen Fällen kann das Experiment ein drittes Mal durchgeführt werden, sodass zwischen $12$ und $17$ Gramm Antimaterie vorliegen. Im ungünstigsten Fall muss das Experiment dreimal durchgeführt werden, was insgesamt $30$ kostet. Der Gewinn beträgt dann $(12\cdot 10^9-30)=11\,999\,999\,970$.

Schreiben Sie ein Programm, das den maximalen garantiert erzielbaren Gewinn $x$ bestimmt.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen: $n$, die Anzahl der Experimentarten, und $a$, die maximal zulässige Menge Antimaterie im Behälter ($1\le n\le 100$, $1\le a\le 2\,000\,000$).

Die folgenden $n$ Zeilen enthalten jeweils drei ganze Zahlen $l_i$, $r_i$ und $c_i$: die minimale und maximale Menge Antimaterie, die durch ein Experiment der Art $i$ erzeugt wird, sowie dessen Kosten ($1\le l_i\le r_i\le a$, $1\le c_i\le 100$).

Ausgabe

Geben Sie eine ganze Zahl aus: den maximalen garantiert erzielbaren Gewinn $x$.

Beispiele

Eingabe 1

1 17
4 6 10

Ausgabe 1

11999999970

Eingabe 2

2 11
2 2 100
3 5 5

Ausgabe 2

9999999890

Teilaufgaben