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
#include <cstdio>
#include <cstring>
#include <numeric>
#include <algorithm>

const int N = 1000 + 10, E = N * N, INF = 0x3f3f3f3f;

int s, t;
int adj[N], to[E], next[E], cap[E];

void link(int a, int b, int c) {
  static int cnt = 2;
  to[cnt] = b, next[cnt] = adj[a], cap[cnt] = c, adj[a] = cnt++;
  to[cnt] = a, next[cnt] = adj[b], cap[cnt] = 0, adj[b] = cnt++;
}

int h[N], gap[N];

int dfs(int a, int df) {
  if (a == t) return df;
  int res = 0;
  for (int i = adj[a]; i; i = next[i]) {
    int b = to[i];
    if (cap[i] && h[a] == h[b] + 1) {
      int f = dfs(b, std::min(df - res, cap[i]));
      cap[i] -= f;
      cap[i ^ 1] += f;
      res += f;
    }
    if (res == df) return res;
  }
  if (--gap[h[a]] == 0) h[s] = t + 1;
  ++gap[++h[a]];
  return res;
}

int flow() {
  memset(h, 0, sizeof h);
  memset(gap, 0, sizeof gap);
  int res = 0;
  while (h[s] <= t) res += dfs(s, INF);
  return res;
}

int n, m, l[N], r[N], c[N];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d%d%d", &l[i], &r[i], &c[i]);
  static int a[N];
  int tot = 0;
  for (int i = 1; i <= n; ++i) a[++tot] = l[i], a[++tot] = r[i];
  std::sort(a + 1, a + tot + 1);
  tot = std::unique(a + 1, a + tot + 1) - a - 1;
  s = n + tot, t = s + 1;
  for (int i = 1; i <= n; ++i) link(s, i, c[i]);
  for (int i = 1; i < tot; ++i) link(i + n, t, m * (a[i + 1] - a[i]));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j < tot; ++j)
      if (l[i] <= a[j] && a[j + 1] <= r[i])
        link(i, j + n, a[j + 1] - a[j]);
  puts(std::accumulate(c + 1, c + n + 1, -flow()) == 0 ? "TAK" : "NIE");
  return 0;
}