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 nalaze u datoteci let.in) 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 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 u kojoj dijamant pada i momenat u kojem će dijamant dotaći dno ekrana.

Izlaz:

(Izlazne podatke upisati u datoteku let.out) U prvom redu ispisati maksimalnu cenu dijamanata koje 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 (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).

/*
  Drzavno takmicenje 2008
  Zadatak: poruka
  Autor: Slobodan Mitrovic, Deronje

  Zadatak se moze resiti dinamickim programiranjem. Naime, dp[k][t] cuva najvecu vrednost
  koja se moze dobiti u k-toj traci u momentu t.
  Vremena u kojima dijamanti dodiruju dno ekrana se sortiraju u neopadajucem poretku.
  Nakon toga prolazimo kroz sve momente i za svaku traku u datom momentu racunamo
  najbolju vrednost koja je jednaka
  max(ako smo u momentu t-1 bili u susednoj traci pa se pomerili u k;
      ako smo u momentu t-1 bili u traci k) + 
    vrednost dijamanat koji su dotakli dno ekrana u k-toj traci u momentu t
    
  NAPOMENA: Primetimo da se stanje u momentu t racuna samo preko stanja
            u momentu t-1, shodno tome, ne moramo cuvati stanja kroz sve momente
            nego samo za prethodni momenat cime se smanjuje memorijska slozenost.
*/

#include <iostream>
#include <cstdio>

using namespace std;

struct mytype{
  int l, t;
  long long c;
  mytype(){
  }
    
  friend bool operator <(const mytype &a, const mytype &b){
    if (a.t < b.t)
      return true;
    else if (a.t > b.t)
      return false;
    else
      return a.l < b.l;
  }
};

long long dp[50][100000 + 1];

int main(){
  FILE* fin;
  FILE* fout;
   fin = fopen("let.in", "r");
  fout = fopen("let.out", "w");
  int n, k, T, i;
  fscanf(fin, "%d %d %d", &k, &n, &T);
  mytype d[n];
  for (i = 0; i < n; i++){
    fscanf(fin, "%I64d %d %d", &d[i].c, &d[i].l, &d[i].t);
    d[i].l--;
  }
  sort(d, d + n);
  memset(dp, 128, sizeof(dp));
  dp[0][0] = 0;
  int lidx = 0;
  long long sum;
  long long *cur;
  for (int t = 1; t <= T; t++)
    for (i = 0; i < k; i++){
      sum = 0;
      while (lidx < n && d[lidx].t == t && d[lidx].l == i)
        sum += d[lidx++].c;
      
      cur = &dp[i][t];
      *cur = dp[i][t - 1] + sum;
      if (i > 0)
        *cur >?= dp[i - 1][t - 1] + sum;
      if (i + 1 < k)
        *cur >?= dp[i + 1][t - 1] + sum;
    }

  sum = 0LL;
  for (i = 0; i < k; i++)
    sum = max(sum, dp[i][T]);

  fprintf(fout, "%I64d\n", sum);
  fclose(fin);
  fclose(fout);
  return 0;
}