Mladi Joško igra novu igricu. U igrici on kontrolira čovječuljka koji mora što prije doći od početka do kraja nivoa. Nivo koji Joško prelazi izgleda ovako:

Dakle, on mora doći od početka do kraja, gdje je početak najljevija pozicija na najvišoj dužini, a kraj je najdesnija pozicija na najnižoj dužini. Joško se po dužinama kreće slijeva na desno. U bilo kojem trenutku Joško može odlučiti “propasti” kroz trenutnu dužinu sve dok se ne zaustavi na prvoj dužini ispod njega. Taj postupak može ponoviti koliko god puta želi jer na njega ne troši vrijeme! Zato što su dužine različito obojene nije uvijek jednaka brzina kretanja po svim dužinama! Po nekim dužinama Joško se kreće sporije, a po nekima brže.

Jedan način, ne nužno najbolji, obilaženja gore navedenog primjera izgledao bi otprilike ovako.

Tvoj je zadatak pomoći Jošku i pronaći najkraće vrijeme potrebno kako bi Joško doveo čovječuljka od početka do kraja, koristeći gore navedena pravila kretanja. Napomena: Rješenje će uvijek postojati.

Ulazni podaci

U prvom redu nalaze se dva prirodna broja \(N\) i \(M\) \((1 \leq N \leq 100, 1 \leq M \leq 100 000)\) koji označavaju broj razina (dužina) i horizontalnu (vodoravnu) udaljenost najljevije točke neke dužine i najdesnije točke neke dužine.

U sljedećih \(N\) redova nalaze se po tri cijela broja \(L\), \(D\), \(T\) \((0 \leq L \leq D \leq M, 1 \leq T \leq 10 000)\) koji predstavljaju jednu dužinu, poretkom od najviše do najniže razine. Brojevi \(L\) i \(D\) predstavljaju horizontalnu (vodoravnu) udaljenost lijeve i desne točke dužine od lijeve točke najljevije dužine. Broj \(T\) predstavlja vrijeme potrebno za prelazak jedinične duljine ove dužine.

Npr., ukoliko je \(T = 3\), utoliko će vrijeme potrebno za prolaz dužine duljine \(4\) biti jednako \(3*4 = 12\).

Izlazni podaci

U prvi red ispiši najmanji broj jedinica vremena koje će Joškovom čovječuljku biti potrebne kako bi došao od početka do kraja nivoa.

Bodovanje

U test primjerima ukupno vrijednim \(30\%\) bodova vrijedit će da je početak dužine na \(N\)-toj razini između početka i kraja dužine na \(N-1\) razini, i da je kraj dužine na \(N\)-toj razini desnije od kraja dužine na \(N-1\) razini.

U test primjerima ukupno vrijednim \(30\%\) bodova vrijedit će da je vrijeme potrebno za prelazak jedinične duljine po razinama rastući, od najviše do najniže razine.

U test primjerima ukupno vrijednim \(50\%\) bodova vrijedit će da je \(M \leq 100\).

Primjeri test podataka

Ulaz

4 10 
0 5 3
2 6 4
1 3 2
6 10 3

Izlaz

31

Objašnjenje

Približan primjer onome sa slike u tekstu zadatka. Minimalno rješenje se postiže na sljedećem prolazu: \(0 \rightarrow 5\) na prvoj razini (\(5 * 3 = 15\) jedinica vremena), prelazak na razinu ispod, \(5 \rightarrow 6\) na drugoj razini (\(1 * 4 = 4\) jedinica vremena), prelazak na posljednju razinu, \(6 \rightarrow 10\) (\(4*3=12\) jedinica vremena). Ukupno je to \(15+4+12=31\) jedinica vremena.

Ulaz

4 10
0 5 5
3 6 7
6 8 9
7 10 2

Izlaz

47

Objašnjenje

Primjer gdje vrijedi prvo ograničenje iz sekcije bodovanja.

Ulaz

4 10
0 5 3
2 6 4
1 3 5
6 10 6

Izlaz

43

Objašnjenje

Primjer gdje vrijedi drugo ograničenje iz sekcije bodovanja.