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

using namespace std;

struct graph {
  typedef int flow_type;
  struct edge {
    int src, dst;
    flow_type capacity, flow;
    size_t rev;
  };
  int n;
  vector<vector<edge>> adj;
  graph(int n) : n(n), adj(n) { }

  void add_edge(int src, int dst, flow_type capacity) {
  	// cout << src << " " << dst << " " << capacity << endl;
    adj[src].push_back({src, dst, capacity, 0, adj[dst].size()});
    adj[dst].push_back({dst, src, 0, 0, adj[src].size() - 1});
  }

  flow_type max_flow(int s, int t) {
    vector<flow_type> excess(n);
    vector<int> dist(n), active(n), count(2*n);
    queue<int> Q;
    auto enqueue = [&](int v) { 
      if (!active[v] && excess[v] > 0) { active[v] = true; Q.push(v); } 
    };
    auto push = [&](edge &e) {
      flow_type f = min(excess[e.src], e.capacity - e.flow);
      if (dist[e.src] <= dist[e.dst] || f == 0) return;
      e.flow += f;
      adj[e.dst][e.rev].flow -= f;
      excess[e.dst] += f;    
      excess[e.src] -= f;
      enqueue(e.dst);
    };

    dist[s] = n; active[s] = active[t] = true;
    count[0] = n-1; count[n] = 1;
    for (int u = 0; u < n; ++u)
      for (auto &e: adj[u]) e.flow = 0;
    for (auto &e: adj[s]) {
      excess[s] += e.capacity;
      push(e);
    }
    while (!Q.empty()) {
      int u = Q.front(); Q.pop();
      active[u] = false;

      for (auto &e: adj[u]) push(e);
      if (excess[u] > 0) {
        if (count[dist[u]] == 1) {
          int k = dist[u]; // Gap Heuristics
          for (int v = 0; v < n; v++) {
            if (dist[v] < k) continue;
            count[dist[v]]--;
            dist[v] = max(dist[v], n+1);
            count[dist[v]]++;
            enqueue(v);
          }
        } else {
          count[dist[u]]--; // Relabel
          dist[u] = 2*n;
          for (auto &e: adj[u]) 
            if (e.capacity > e.flow)
              dist[u] = min(dist[u], dist[e.dst] + 1);
          count[dist[u]]++;
          enqueue(u);
        }
      }
    }

    flow_type flow = 0;
    for (auto e: adj[s]) flow += e.flow;
    return flow;
  }
};

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	int p[n], k[n], c[n];
	vector<int> timeline;
	long long oczek = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &p[i], &k[i], &c[i]);
		k[i]--; 
		oczek += (long long)(c[i]);
		timeline.push_back(p[i]);
		// timeline.push_back(p[i] - 1);
		timeline.push_back(k[i] + 1);
		timeline.push_back(k[i]);
	}
	sort(timeline.begin(), timeline.end()); 
	timeline.erase(unique(timeline.begin(), timeline.end()), timeline.end());
	timeline.push_back(timeline.back() + 1);
	graph g(1 + timeline.size() - 1 + n + 1);
	int aktP = timeline[0];
	for (int i = 1; i < timeline.size(); i++) {
		// [aktP, timeline[i] - 1]
		// cout << aktP << "-" << timeline[i] - 1 << endl;
		for (int j = 0; j < n; j++) {
			// cout << "AKTP: " << aktP << " " << p[j] << " " << k[j] << endl;
			if (aktP >= p[j] && aktP <= k[j]) {
				g.add_edge(timeline.size() + j, i, (long long)(timeline[i] - aktP));
				// if (!(timeline[i] - 1 >= p[j] && timeline[i] - 1 <= k[j])) {
				// 	puts("KREMOWKA");
				// 	cout << aktP << "-" << timeline[i] - 1 << endl;
				// 	cout << p[j] << " " << k[j] << endl;
				// }
			}
		}
		g.add_edge(i, timeline.size() + n, (long long)(timeline[i] - aktP) * (long long)m);
		aktP = timeline[i];
	}
	for (int i = timeline.size(); i < timeline.size() + n; i++) {
		g.add_edge(0, i, c[i - timeline.size()]);
	}
	if (g.max_flow(0, timeline.size() + n) == oczek) puts("TAK");
	else puts("NIE");
	//printf("%d\n", g.max_flow(0, timeline.size() + n));
	return 0;
}