1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_map>
#include <queue>
#define pb push_back
#define sz size()
using namespace std;
typedef vector<int> vi;

struct zadanie {
  int p, k, c;
};

int flow(vector<vi>& G) {
  const int end = G.sz-1;
  int f = 0;
  while(true) {
    vi parent(G.sz, -1);
    queue<int> kju;
    kju.push(0);
    parent[0] = 0;
    while(kju.sz && parent[end] == -1) {
      int a = kju.front(); kju.pop();
      for(int b=0; b<G[a].sz; ++b) {
	if(parent[b] == -1 && G[a][b] > 0) {
	  parent[b] = a;
	  kju.push(b);
	}
      }
    }
    if(parent[end] == -1) return f;
    int f1 = G[parent[end]][end];
    for(int a=end; parent[a] != a; a=parent[a])
      f1 = min(f1, G[parent[a]][a]);
    for(int a=end; parent[a] != a; a=parent[a]) {
      G[parent[a]][a] -= f1;
      G[a][parent[a]] += f1;
      // printf(". %d->%d\t%d\n", parent[a], a, G[parent[a]][a]);
      // printf(". %d->%d\t%d\n", a, parent[a], G[a][parent[a]]);
    }
    f += f1;
  }
}

int main() {
  int n, m; scanf("%d%d", &n, &m);
  vector<zadanie> zad(n+1);
  set<int> ts;
  int sumc = 0;
  for(int i=1; i<=n; ++i) {
    scanf("%d%d%d", &zad[i].p, &zad[i].k, &zad[i].c);
    ts.insert(zad[i].p);
    ts.insert(zad[i].k);
    sumc += zad[i].c;
  }
  vi konce(ts.begin(), ts.end());
  unordered_map<int,int> mk;
  for(int i=0; i<konce.sz; ++i) {
    mk[konce[i]] = i;
    //printf("%d -> %d\n", konce[i], i);
  }
  int b = konce.sz;

  vector<vi> G(1+n+b, vi(1+n+b, 0));
  for(int i=1; i<=n; ++i) {
    G[0][i] = zad[i].c;
    for(int j=mk[zad[i].p]; j+1<konce.sz && konce[j]<zad[i].k; ++j) {
      G[i][n+1+j] = konce[j+1] - konce[j];
    }
  }
  for(int j=0; j+1<konce.sz; ++j)
    G[n+1+j][n+b] = m*(konce[j+1] - konce[j]);

  //  for(int a=0; a<G.sz; ++a)
  //    for(int b=0; b<G[a].sz; ++b)
  //      if(G[a][b])
  //	printf("%d->%d:\t%d\n", a, b, G[a][b]);

  puts(flow(G) == sumc ? "TAK" : "NIE");
}