S - Spojenia

Ondrej si naplánoval výlet verne kopírujúci dej jeho obľúbeného filmu. Zistil si informácie o všetkých prepravcoch, ktorí fungujú na danej trase. Každý prepravca prevádzkuje vlastnú linku s určeným nástupom (Z), výstupom (K) a cenou za prepravu (H), pričom nástup je potrebné dodržať, no vystúpiť sa dá aj skôr. Samozrejme, Ondrej môže časť alebo celú trasu prejsť pešo, no aj takto prejdený dielik má istú cenu C. Koľko najmenej by ho stála cesta od pozície 0 po N?

Úloha

Pre daný popis zistite minimálnu cenu dopravy.

Vstup

V prvom riadku súboru sa nachádzajú čísla P, N a C

Nasleduje P riadkov s popisom ponúk prepravy - trojicou čísel Z, K a H

1 ≤ P ≤ 1 000
1 ≤ N ≤ 10 000
1 ≤ C ≤ 20
0 ≤ Z < K ≤ N
0 ≤ H < C*(K-Z)

Výstup

Výstupom programu je minimálna cena dopravy.

Príklad

Vstup:

5 10 10
0 10 100
1 4 20
2 8 80
3 5 20
6 8 5

Výstup:

75

Vysvetlenie
Pešo prejde úseky 0-1, 4-6 a 8-10 (v hodnote spolu 5*10) a použije prepravu 1-4 a 6-8 v hodnote 25.