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
127
128
129
130
131
132
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <list>
#include <algorithm>

#define N 1000000

using namespace std;

class Zadanie {
	public:
		int numer;
		int poczatek;
		int koniec;
		int czas_wykonania;
		int niezmiennik;
		int liczba_uzyc;
	
	Zadanie(int numer, int poczatek, int koniec, int czas_wykonania) {
		this->numer = numer;
		this->poczatek = poczatek;
		this->koniec = koniec;
		this->czas_wykonania = czas_wykonania;
		this->liczba_uzyc = 0;
	}
};

void drukuj(list<Zadanie> zadania) {
//	list<Zadanie>::iterator it;
//	for (it = zadania.begin(); it != zadania.end(); ++it) {
//		printf("%d (%d %d) %d\n", it->numer, it->poczatek, it->koniec, it->czas_wykonania);
//	}
}

bool sort_function(Zadanie a, Zadanie b) {
	return (a.poczatek < b.poczatek);
}

bool sort_function2(Zadanie a, Zadanie b) {
	return (a.niezmiennik < b.niezmiennik);
}

int main() {
	int n, m;
	
	int p, k, c;
	
	list<Zadanie> zadania;
	list<Zadanie> biezace_zadania;
	
	scanf("%d %d\n", &n, &m);
	
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d\n", &p, &k, &c);
		
		zadania.push_back(Zadanie(i, p, k, c));
	}
	
	zadania.sort(sort_function);
	
	drukuj(zadania);
	
	for (int i = 0; i < N; i++) {
		bool dodano = false;
		
		while(zadania.size() > 0) {
			if (zadania.front().poczatek == i) {
				Zadanie zadanie = zadania.front();
				zadania.pop_front();
				
				zadanie.niezmiennik = i + zadanie.koniec - zadanie.poczatek - zadanie.czas_wykonania;
				
				biezace_zadania.push_back(zadanie);
				dodano = true;
			
			} else {
				break;
			}
		}
		
		if (dodano) {
			biezace_zadania.sort(sort_function2);
		}
		
		drukuj(biezace_zadania);
		
		list<Zadanie> pobrane_zadania;
		
		for (int j = 0; j < m; j++) {
			if (biezace_zadania.size() == 0) {
				break;
			}
			
			Zadanie zadanie = biezace_zadania.front();
			biezace_zadania.pop_front();
			
			if (zadanie.koniec <= i) {
				printf("NIE\n");
				return 0;
			}
			
			zadanie.liczba_uzyc++;
			zadanie.niezmiennik++;
			
			if (zadanie.liczba_uzyc < zadanie.czas_wykonania) {
				pobrane_zadania.push_back(zadanie);
			}
		}
		
		if (pobrane_zadania.size() > 0) {
			list<Zadanie> lista;
				
			merge(biezace_zadania.begin(), biezace_zadania.end(), pobrane_zadania.begin(), pobrane_zadania.end(), back_inserter(lista), sort_function2);
			
			biezace_zadania = lista;
		}
		
		if (zadania.size() == 0 && biezace_zadania.size() == 0) {
			break;
		}
	}
	
	if (biezace_zadania.size() == 0) {
		printf("TAK\n");
	
	} else {
		printf("NIE\n");
	}
	
	return 0;
}