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
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;

typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<int,int> pii;
#define mp make_pair

#define REP(i,n) for (int i=0,___=(n); i<___; ++i)
#define FOR(i,a,b) for (int i=(a),___=(b); i<=___; ++i)
#define FORD(i,a,b) for (int i=(a),___=(b); i>=___; --i)

int read() { int n; scanf("%d", &n); return n; }
ll readl() { ll n; scanf("%lld", &n); return n; }
char readc() { static char s[32]; scanf("%s", s); return *s; }



typedef pair<int, pair<int, int> > tr;
#define m3(a,b,c) make_pair((a), make_pair((b), (c)))
#define st first
#define nd second.first
#define rd second.second

bool cmp(const tr &a, const tr &b) {
	return a.rd < b.rd || (a.rd == b.rd && a.nd < b.nd);
}

bool solve() {
	int n = read();
	int m = read();

	priority_queue<tr> q;
	REP(i, n) {
		int p = read();
		int k = read();
		int c = read();
		q.push(m3(-p, c, k - p - c));
	}

	while (q.size() > m) {
		vector<tr> v;
		v.push_back(q.top());
		q.pop();
		while (!q.empty() && q.top().st == v[0].st) {
			v.push_back(q.top());
			q.pop();
		}
		if (v.size() <= m) {
			if (q.empty()) return true;
			int diff = v[0].st - q.top().st;
			REP(i, v.size()) {
				v[i].st -= diff;
				v[i].nd -= diff;
				if (v[i].nd > 0) {
					q.push(v[i]);
				}
			}
		} else {
			sort(v.begin(), v.end(), cmp);
			if (v[m].rd <= 0) return false;
			FOR(i, m, v.size()-1) {
				v[i].st--;
				v[i].rd--;
				q.push(v[i]);
			}
			REP(i, m) {
				v[i].st--;
				v[i].nd--;
				if (v[i].nd > 0) {
					q.push(v[i]);
				}
			}
		}
	}

	return true;
}

int main() {
	printf("%s\n", solve() ? "TAK" : "NIE");

	return 0;
}