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
#include<bits/stdc++.h>
using namespace std;

const long long DUZO = 1e16;

struct flow { 
	long long n;
	vector<vector<long long>> c,adj;
	vector<long long> p,dist,beg;
	
	flow(long long _n): n(_n) {
		adj.resize(n+1);
		c.resize(n+1);
		for (long long i = 0; i <= n; ++ i)
			c[i].resize(n+1);
		p.resize(n+1);
		dist.resize(n+1);		
		beg.resize(n+1);
	}
	
	void addEdge(long long a, long long b, long long d) {
		c[a][b] += d;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	bool Bfs(long long s, long long t) {
		for (long long i = 0; i <= n; ++ i)
			dist[i] = DUZO;
		dist[s] = 0;
		queue<long long> Q; Q.push(s);
		while (!Q.empty()) {
			long long w = Q.front(); Q.pop();
			for (auto r: adj[w]) {
				if (c[w][r] > 0 && dist[r] == DUZO) {
					dist[r] = dist[w] + 1;
					p[r] = w;
					Q.push(r);
				}
			}
		}
		return dist[t] != DUZO;
	}
	
	long long Dfs(long long v, long long t, long long mn) {
		if (mn == 0 || v == t) return mn;
		long long res = 0;
		for (long long& i = beg[v]; i < (long long) adj[v].size(); ++ i) {
			long long u = adj[v][i];
			if (c[v][u] > 0 && dist[u] == dist[v] + 1) {
				long long x = Dfs(u, t, min(mn,c[v][u]));
				mn -= x; res += x;
				c[v][u] -= x; c[u][v] += x;
			}
			if (mn == 0) {
				break;
			}
		}
		return res;
	}
	
	long long maxFlow(long long s, long long t) {
		long long res = 0;
		while (Bfs(s,t)) {
			for (long long i = 0; i <= n; ++ i) beg[i] = 0;
			res += Dfs(s, t, DUZO);
		}	
		return res;
	}	
};

const long long MX = 10005;
long long p[MX], k[MX], c[MX], n, m;
long long pocz[MX], konc[MX], suma;
set<long long> S;

flow G(1000);

int main() 
{

	scanf("%lld%lld", &n, &m);
	for (long long i = 1; i <= n; ++ i)
	{
		scanf("%lld%lld%lld", &p[i], &k[i], &c[i]);
		S.insert(p[i]); S.insert(k[i]);
		suma += c[i];
	}
		
	long long x = 2, pre = 0;
	for (auto r: S) 
	{
		pocz[x] = pre; konc[x] = r; pre = r;
		if (konc[x] > pocz[x]) 
		{
			G.addEdge(1, x, (konc[x] - pocz[x]) * m);		
			x ++; 
		}
	}
	long long ujs = x+n, kn = x-1;
	
	for (long long i = 1; i <= n; ++ i)
	{
		for (long long j = 2; j <= kn; ++ j)
		{
			long long d = min(konc[j], k[i]) - max(pocz[j], p[i]);
			if (d > 0)
				G.addEdge(j,x,d);
		}
		G.addEdge(x,ujs,c[i]);
		x++;
	}

	puts(G.maxFlow(1,ujs) == suma ? "TAK" : "NIE");
		
	return 0;
}