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
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int n, m, dlugosc, liczba, zmiany, wartosc, ile, punkt, czas;
int p[105];
int k[105];
int c[105];
int zapas[105];
int tab[105];

struct akcja
{
	int czas;
	int rodzaj;
	int element;
};

akcja pomoc;
vector <akcja> v;

set <int> elementy;
set <int>::iterator sit;

bool comp (int F, int S)
{
	return zapas[F] > zapas[S];
}

bool comp2 (akcja F, akcja S)
{
	return F.czas < S.czas;
}

int main ()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d%d%d", &p[i], &k[i], &c[i]);
		zapas[i] = k[i] - p[i] - c[i];
		pomoc.czas = p[i];
		pomoc.rodzaj = 1;
		pomoc.element = i;
		v.push_back(pomoc);
		pomoc.czas = k[i];
		pomoc.rodzaj = 0;
		v.push_back(pomoc);
	}
	sort(v.begin(), v.end(), comp2);
	for (int i = 0; i < 2 * n; ++i)
	{
		if (v[i].rodzaj == 0)
		{
			if (zapas[v[i].element] < 0)
			{
				printf("NIE\n");
				return 0;
			}
			if (elementy.find(v[i].element) != elementy.end()) elementy.erase(v[i].element);
		}
		if (v[i].rodzaj == 1) elementy.insert(v[i].element);
		if (elementy.empty()) continue;
		dlugosc = v[i + 1].czas - v[i].czas;
		if (dlugosc == 0) continue;
		liczba = 0;
		for (sit = elementy.begin(); sit != elementy.end(); ++sit)
		{
			tab[liczba] = *sit;
			liczba++;
		}
		if (m >= liczba) continue;
		sort(tab, tab + liczba, comp);
		czas = v[i].czas;
		while (dlugosc--)
		{
			liczba = 0;
			for (sit = elementy.begin(); sit != elementy.end(); ++sit)
			{
				tab[liczba] = *sit;
				liczba++;
			}
			for (int j = 0; j < liczba; ++j) if (zapas[tab[j]] >= k[tab[j]] - czas) elementy.erase(tab[j]);
			liczba = 0;
			for (sit = elementy.begin(); sit != elementy.end(); ++sit)
			{
				tab[liczba] = *sit;
				liczba++;
			}
			sort(tab, tab + liczba, comp);
			if (m >= liczba) break;
			zmiany = liczba - m;
			for (int j = 0; j < zmiany; ++j) zapas[tab[j]]--;
			czas++;
		}
	}
	printf("TAK\n");
	return 0;
}