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
#include <stdio.h>
#include <iostream>
#include <algorithm>

#include <list>

using namespace std;
struct ProcessDesc
{
	 int p;
	 int k;
	 int c;	
};

struct Capacity
{
	 int p;
	 int k;
	 int m;
	
	Capacity(int p1, int k1, int m1)
	{
		p = p1;
		k = k1;
		m = m1;
	}

};

int sortuj(const ProcessDesc * arg1, const ProcessDesc * arg2)
{
	if (arg1->k == arg2->k) return arg2->p - arg1->p;
	return arg1->k -  arg2->k;
}

int main()
{
	int n = 0;

	int m = 0;

	ProcessDesc processes[200];// = { {3,19,3},{2,8,2}, {3,8,3} };

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> processes[i].p >> processes[i].k >> processes[i].c;
	}


	qsort(processes, n, sizeof(processes[0]), (int(*)(const void *, const void *)) sortuj);

	
	list<Capacity*> capactities;
	capactities.push_back(new Capacity(0, 2000000, m));


	for (int i = 0; i < n; i++)
	{
		ProcessDesc proccess = processes[i];
		
		//int pos = 0;
		list<Capacity*>::iterator  it = capactities.begin();
		
		while (true)
		{
			if( it== capactities.end())
			{
				cout << "NIE";
				return 0;
			}
			Capacity * cap = *it;

			if ((cap->k < proccess.p) || cap->m == 0)
			{
				it++;
				continue;
			}
			if (cap->p > proccess.p)
			{
				proccess.p = cap->p;
				if (proccess.k - proccess.p - proccess.c < 0)
				{
					cout << "NIE";
					return 0;
				}
			}
			if (proccess.p > cap->p)
			{
				int middle = proccess.p;
				Capacity *  newCap = new Capacity(cap->p, middle, cap->m);
				cap->p = middle;
				capactities.insert(it, newCap);				
			}
			int timeslot = cap->k - cap->p;
			if (timeslot > proccess.c)
			{
				timeslot = proccess.c;
				int middle = cap->p + timeslot;
				
				Capacity *  newCap = new Capacity(cap->p, middle, cap->m);
				cap->p = middle;
				capactities.insert(it, newCap);
				cap = newCap;
				it--;
			}
			proccess.c = proccess.c - timeslot;
			cap->m--;
			if (proccess.c == 0)
			{
				
				break;
			}
			else
			{
				proccess.p = cap->k;
			}
			it++;
		}

	}
	cout << "TAK";
	
	return 0;
}