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

const int N = 405;
// const int M = 30;
int beg[N], koniec[N], dur[N];

const long long int inf = 1LL<<60;
long long int f[2*N][2*N], wynik;
long long int target;
int v_size, lay[2*N], wsk[2*N];
queue<int> kol;

bool BFS()
{
	int v;
	kol.push(0);
	lay[0]=1;
	for (int i=1;i<=v_size;i++) lay[i]=0;
	for (int i=0;i<=v_size;i++) wsk[i]=0;
	while( kol.empty()==0 )
	{
		v = kol.front();
		kol.pop();
		for (int i=0;i<=v_size;i++)
			if ( lay[i]==0 && f[v][i]>0 )
			{
				lay[i] = lay[v]+1;
				kol.push(i);
			}
	}
	if (lay[v_size]==0) return 0;
	return 1;
}

long long int dfs(int a,long long int d)
{
	long long x=0,y;
	if (a==v_size)
	{
		wynik+=d;
		return d;
	}
	for (;d&&wsk[a]<=v_size;wsk[a]++)
		if (lay[ wsk[a] ] == lay[a]+1)
		{
			y = dfs( wsk[a], min(d, f[a][ wsk[a] ] ) );
			d-=y;
			x+=y; 
			f[a][ wsk[a] ] -=y;
			f[ wsk[a] ][a] +=y;
		}
	return x;
}

void dinic()
{
	while( BFS() ) dfs(0,inf);
}

void init(int n,int m) {
	vector<int> ska;
	for (int i = 1; i <= n; i ++) {
		ska.push_back(beg[i]);
		ska.push_back(koniec[i]);
		target += dur[i];
	}
	ska.push_back(1000 * 1000);
	ska.push_back(1000 * 1000 + 1);
	sort(ska.begin(), ska.end());
	ska.resize(unique(ska.begin(), ska.end()) - ska.begin());
	v_size = n + ska.size() + 1;
	for (int i = 1; i <= n; i ++) {
		//krawędzie odpowiadające za możność zajęcia danego przedziału
		for (int j = 0; j < ska.size() - 1; j ++) {
			if (beg[i] <= ska[j] && ska[j] < koniec[i]) {
				f[i][n + j + 1] = ska[j + 1] - ska[j];
			}
		}
		//krawędzie odpowiadające za konieczność wykonanaia dur[i] zadań
		f[0][i] = dur[i];
	}
	//krawędzie z wątków do końca
	for (int i = 0; i < ska.size() - 1; i++) {
		f[n + i + 1][v_size] = m *(ska[i + 1] - ska[i]);
	}
}

bool da_sie(int n,int m) {
	dinic();
	return target == wynik;
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", beg + i);
		scanf("%d", koniec + i);
		scanf("%d", dur + i);
	}
	init(n, m);
	bool result = da_sie(n, m);
	printf(result ? "TAK" : "NIE");
}