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.

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.

Ulaz:

(Ulazni podaci se učitavaju 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 nredova se nalazi podaci o dijamantima. U i+1-om redu se nalazeprirodni brojevi c_i (1 ≤ c_i ≤ 1000000),l_i (1 ≤ l_i ≤ k) i t_i (1 ≤ t_i≤ 200000), koji redom oznachavaju cenu dijamanta, traka ukojoj dijamant pada i momenat u kojem će dijamant dotaćidno ekrana.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U prvom redu ispisati maksimalnu cenu dijamanatakoje letelica može da pokupi.

Ogranicenja:

• Maksimalno vreme izvršavanja programa je 1.5 sekunda.

Primer 1:

5 11 10
10 1 2
10 1 2
200 3 2
50 3 2
50 3 2
10 4 2
10 4 2
200 5 5
50 1 4
10 2 2
10 2 2

500

Primer 2:

4 9 10
200 4 1
200 4 3
5 1 1
5 1 2
5 1 3
5 1 3
5 1 4
5 1 5
5 1 11

200

Objašnjenje:

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 (primetimoda se igra završava posle 10 sekundi, pa dijamant koji će na dno ekrana dospeti u 11.sekundi ne moće biti uhvaćen).