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
83
84
85
86
#include <iostream>
#include <algorithm>

int n, m;

struct T
{
  int s, e, d;
};

T t[100];
int x = 0;

bool cmp(const T& a, const T& b)
{
  int p = std::max(a.s, x);
  int q = std::max(b.s, x);
  return p < q || (p == q && (a.e -a.d < b.e -b.d || (a.e-a.d == b.e-b.d && a.d < b.d)));
  //return p < q || (p == q && (a.e < b.e || (a.e == b.e && a.d < b.d)));
}

const int inf = 2000000;

int run()
{
  if(n <= m)
    return 1;
  int i;
  int e;
  std::sort(t, t+n, cmp);
  x = t[0].s;
  while(x < inf)
  {
    e = inf;
    i = 0;
    while(i < m && i < n && t[i].s <= x)
    {
      if(x + t[i].d > t[i].e)
      {
        return 0;
      }
      e = std::min(x + t[i].d, e);
      i ++;
    }
    int nextstart = inf;
    int u = (i == 0) ? inf : t[i-1].e;
    for(int j=i; j<n; j++)
    {
      if(t[j].s > x)
      {
        nextstart = t[j].s;
        break;
      }
    }
    for(int j=i; j<n; j++)
    {
      if(t[j].e-t[j].d > x)
        nextstart = std::min(nextstart, t[j].e-t[j].d);
    }
    int y = std::min(nextstart, e);
    int nn = n;
    for(int j=0; j<i; j++)
    {
      t[j].d -= y-x;
      if(t[j].d == 0)
      {
        nn --;
        t[j].s = inf;
      }
    }
    std::sort(t, t+n, cmp);
    n = nn;
    x = y;
  }
  return n == 0;
}

int main()
{
  std::ios::sync_with_stdio(false);
  std::cin >> n >> m;
  for(int i=0; i<n; i++)
    std::cin >> t[i].s >> t[i].e >> t[i].d;
  std::cout << (run() ? "TAK" : "NIE") << std::endl; 
  return 0;
}