let

Ispred Vas se nalazi ekran izdeljen na k vetikalnih traka koje su s leva na desno redom ozna?ene brojevima 1, 2, ..., k. Na dnu ekrana se nalazi letelica koja može da se kre?e kroz trake (iz jedne trake letelica mozhe da pre?e samo u susednu), a kojoj treba 1 sekunda da se pomeri u slede?u traku ekrana. Sa gornjeg dela ekrana pada n dijamanata. Za svaki dijamant je poznata cena c, traka l u kojoj pada (dijamant pada u ta?no jednoj traci) i momenat t u kojem ?e dota?i dno ekrana. Letelica je širine trake i može da pokupi neki dijamant samo ako se celom širinom nalazi u traci u kojoj pada dijamant ta?no u vremenu kada dijamant dotakne dno ekrana. Ako letelica u momentu x krene da prelazi u susednu traku, tada ?e se celom svojom širinom u susednoj traci na?i u momentu x+1. Znachi, ako u momentu x sa trake s krene da prelazi u susednu traku s1 (s1 je ili s-1 ili s+1), tada ?e u traci s pokupiti dijamante koji u trenutku x, a u s1 dijamante koji u trenutku x+1 doti?u dno ekrana. Dok se letelica nalazi u jednoj traci celom širinom, u toj traci može da ostane proizvoljno vreme.
<br><br>
Letelica može da skuplja dijamante t sekundi. U momentu 0 letelica se nalazi u traci 1. Vaš zadatak je da na?ete maksimalnu cenu dijamanata koju letelica može da pokupi za dato vreme.
<br><br>
Ulaz:<br><br>

(Ulazni podaci se citaju sa standardnog ulaza) U prvom redu se nalaze prirodni brojevi brojevi k (1 ? k ? 50), n (1 ? n ? 100000) i T (1 ? T ? 100000). U narednih n redova se nalazi podaci o dijamantima. U i+1-om redu se nalaze prirodni brojevi ci (1 ? ci ? 1000000), li (1 ? li ? k) i ti (1 ? ti ? 200000), koji redom oznachavaju cenu dijamanta, traka u kojoj dijamant pada i momenat u kojem ?e dijamant dota?i dno ekrana.<br><br>

Izlaz:<br><br>

(Izlazne podatke ispisati na standardni izlaz) U prvom redu ispisati maksimalnu cenu dijamanata koje letelica može da pokupi.<br><br>
Primeri:<br><br>
Ulaz:
5 11 10<br>
10 1 2<br>
10 1 2<br>
200 3 2<br>
50 3 2<br>
50 3 2<br>
10 4 2<br>
10 4 2<br>
200 5 5<br>
50 1 4<br>
10 2 2<br>
10 2 2<br>
<br>
Izlaz:<br>
500<br>
<br>Ulaz:<br>
4 9 10<br>
200 4 1<br>
200 4 3<br>
5 1 1<br>
5 1 2<br>
5 1 3<br>
5 1 3<br>
5 1 4<br>
5 1 5<br>
5 1 11<br><br>
Izlaz:<br>
200<br>
<br>
Objašnjenje:<br>

Na po?etku igre letelica po?inje kretanje prema traci 4. U traku 4 stiže u 3: sekundi i kupi dijamant cene 200. Nakon toga nema vremena da pokupi još nešto (primetimo da se igra završava posle 10 sekundi, pa dijamant koji ?e na dno ekrana dospeti u 11. sekundi ne mo?e biti uhva?en).