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

struct task{
	int p,k,c;
	set<pair<int,int> > s;
} T[100];

bool fct(const task& a, const task &b) {
	if (a.k==b.k) return a.c>b.c;
	return a.k<b.k;	
	}

struct proc{int p,k;
	set<pair<int,int> > s;
	proc() {s.insert(make_pair(0,10000000));}
} P[100];

int main() {
	int n,m;
	cin >> n >> m;
	for (int i=0;i<n;i++) {
		cin >> T[i].p >> T[i].k >> T[i].c;
		T[i].s.insert(make_pair(T[i].p,T[i].k));
	}
	sort(T,T+n,fct);
	//for (int i=0;i<n;i++)	cout << T[i].p << T[i].k << T[i].c << endl;
	for (int t=0;t<n;t++) {
		task & z = T[t];
		for (int p=0; z.c>0 && p<m;p++) {
			proc & r = P[p];
			set<pair<int,int> >::iterator zit=z.s.begin(), rit=r.s.begin(), it;
			while (z.c>0 && zit!=z.s.end() && rit!=r.s.end()) {
				if (zit->first >= rit->second) {rit++; continue;}
				if (zit->second <= rit->first) {zit++; continue;}
				//printf("r:%d %d  z:%d %d c=%d\n",rit->first,rit->second,zit->first,zit->second,z.c);
				if (zit->second < rit->second) {
					if (zit->first > rit->first) {
						int k = zit->second;
						if (zit->second - zit->first > z.c) k = zit->first+z.c;
						z.c -= k - zit->first;
						r.s.insert(make_pair(rit->first,zit->first));
						r.s.insert(make_pair(k,rit->second));
					} else if (zit->first == rit->first) {
						int k = zit->second;
						if (zit->second - zit->first > z.c) k = zit->first+z.c;
						z.c -= k - zit->first;
						r.s.insert(make_pair(k,rit->second));
					} else {
						int k = zit->second;
						if (zit->second - rit->first > z.c) k = rit->first+z.c;
						z.c -= k - rit->first;
						r.s.insert(make_pair(k,rit->second));
						z.s.insert(make_pair(zit->first,rit->first));
					}
				} else if (zit->second==rit->second) {
					if (zit->first > rit->first) {
						if (zit->second - zit->first > z.c) {
							r.s.insert(make_pair(rit->first,zit->first));
							r.s.insert(make_pair(zit->first+z.c,rit->second));
							z.c =0;
						} else {
							z.c -= zit->second-zit->first;
							r.s.insert(make_pair(rit->first,zit->first));
						}
					} else if (zit->first == rit->first) {
						if (zit->second - zit->first > z.c) {
							r.s.insert(make_pair(zit->first+z.c,rit->second));
							z.c =0;
						} else {
							z.c -= zit->second-zit->first;
						}
					} else {
						if (zit->second - rit->first > z.c) {
							r.s.insert(make_pair(rit->first+z.c,rit->second));
							z.c = 0;
						} else {
							z.c -= zit->second - rit->first;
							z.s.insert(make_pair(zit->first,rit->first));
						}
					}
				} else { // zit->second > rit->second
					if (zit->first > rit->first) {
						if (rit->second - zit->first > z.c) {
							r.s.insert(make_pair(rit->first,zit->first));
							r.s.insert(make_pair(zit->first+z.c,rit->second));
							z.c = 0;
						} else {
							z.c -= rit->second - zit->first;
							r.s.insert(make_pair(rit->first,zit->first));
							z.s.insert(make_pair(rit->second,zit->second));
							//puts("*7");
						}
					} else if (zit->first == rit->first) {
						if (rit->second - zit->first > z.c) {
							r.s.insert(make_pair(zit->first+z.c,rit->second));
							z.c = 0;
						} else {
							z.c -= rit->second - zit->first;
							z.s.insert(make_pair(rit->second,zit->second));
							//puts("*8");
						}
					} else {
						if (rit->second - rit->first > z.c) {
							r.s.insert(make_pair(rit->first+z.c,rit->second));
							z.c = 0;
						} else {
							z.c -= rit->second - rit->first;
							z.s.insert(make_pair(zit->first,rit->first));
							z.s.insert(make_pair(rit->second,zit->second));
							//puts("*9");
						}
					}
				}
				it = zit; if (zit!=z.s.begin()) zit--; else zit++; z.s.erase(it);
				it = rit; if (rit!=r.s.begin()) rit--; else rit++; r.s.erase(it);
			}
		}
		if (z.c>0) {
			cout << "NIE";
			return 0;
		}
	}
	cout << "TAK";
	return 0;
}