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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
#define REP(a,b) for(int a=0; a<(b); ++a)
#define FWD(a,b,c) for(int a=(b); a<(c); ++a)
#define FWDS(a,b,c,d) for(int a=(b); a<(c); a+=d)
#define BCK(a,b,c) for(int a=(b); a>(c); --a)
#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) ((int)(a).size())
#define VAR(x) #x ": " << x << " "
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define gcd __gcd
#define x first
#define y second
#define st first
#define nd second
#define pb push_back

using namespace std;

template<typename T> ostream& operator<<(ostream &out, const vector<T> &v){ out << "{"; for(const T &a : v) out << a << ", "; out << "}"; return out; }
template<typename S, typename T> ostream& operator<<(ostream &out, const pair<S,T> &p){ out << "(" << p.st << ", " << p.nd << ")"; return out; }

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int dx[] = {0,0,-1,1}; //1,1,-1,1};
const int dy[] = {-1,1,0,0}; //1,-1,1,-1};

template<class capacity_type, capacity_type EPS, capacity_type INF, int N>
struct Dinic {
  struct edge {
    int v, r;
    capacity_type c;
  };
  array<vector<edge>, N> out;
  void clear(int _n) {
    for (int i = 0; i < _n; ++i) out[i].clear();
  }

  void add_edge(int a, int b, capacity_type c) {
    out[a].push_back(edge{b, SIZE(out[b]), c});
    out[b].push_back(edge{a, SIZE(out[a])-1, 0});
  }

  int n, s, t;
  array<int, N> depth;
  queue<int> Q;
  bool bfs() {
    memset(depth.data(), -1, n * sizeof(int));
    Q.push(s);
    depth[s] = 0;
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      if (u == t) break;
      for (edge e : out[u])
        if (e.c > EPS && depth[e.v] == -1) {
          Q.push(e.v);
          depth[e.v] = depth[u] + 1;
        }
    }
    while (!Q.empty()) Q.pop();
    return depth[t] != -1;
  }

  array<int, N> ind;
  capacity_type dfs(int u, capacity_type f) {
    if (u == t) return f;
    capacity_type tc = 0;
    while (f > EPS && ind[u] < SIZE(out[u])) {
      edge &e = out[u][ind[u]];
      ++ind[u];
      if (depth[u] + 1 == depth[e.v] && e.c > EPS) {
        capacity_type c = dfs(e.v, min(f, e.c));
        f -= c;
        tc += c;
        e.c -= c;
        out[e.v][e.r].c += c;
      }
    }
    return tc;
  }

  capacity_type flow(int nodes, int source, int sink) {
    n = nodes;
    s = source;
    t = sink;
    capacity_type f = 0;
    while (bfs()) {
      memset(ind.data(), 0, n * sizeof(int));
      f += dfs(s, INF);
    }
    return f;
  }
};

Dinic<int, 0, 1000*1000*1000, 1010> dinic;

int n, m, s;
int P[110], K[110], C[110];
vector<int> G;

int main(){
	scanf("%d %d", &n, &m);
	FWD(i,1,n+1){
		scanf("%d %d %d", &P[i], &K[i], &C[i]);
		G.push_back(P[i]);
		G.push_back(K[i]);
		s += C[i];
	}
	sort(G.begin(), G.end());
	G.erase(unique(G.begin(), G.end()), G.end());
	FWD(i,1,n+1){
		dinic.add_edge(0, i, C[i]);
		FWD(j,0,SIZE(G)-1)
			if(P[i] <= G[j] && G[j] < K[i])
				dinic.add_edge(i, n+1+j, G[j+1]-G[j]);
	}
	FWD(j,0,SIZE(G)-1)
		dinic.add_edge(n+1+j, n+1+SIZE(G)-1, m*(G[j+1]-G[j]));
	if(dinic.flow(n+1+SIZE(G), 0, n+1+SIZE(G)-1) == s)
		printf("TAK\n");
	else
		printf("NIE\n");
	return 0;
}