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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

/**
 * Created by konrad on 26.11.16.
 */
public class sze {
    public static class IN {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = null;

        private void prepare() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
        }

        public int getInt() throws IOException {
            prepare();
            return Integer.parseInt(st.nextToken());
        }

        public long getLong() throws IOException {
            prepare();
            return Long.parseLong(st.nextToken());
        }

        public String getString() throws IOException {
            prepare();
            return st.nextToken();
        }
    }


//    // FROM TOPCODER : https://www.topcoder.com/community/data-science/data-science-tutorials/maximum-flow-section-2/
//
//
//// Nodes, Arcs, the source node and the sink node
//int n, m, source, sink;
//
//// Matrixes for maintaining
//// Graph and Flow
//int G[N][N], F[N][N];
//
//int pi[N]; // predecessor list
//int CurrentNode[N]; // Current edge for each node
//
//int queue[N]; // Queue for reverse BFS
//
//int d[N]; // Distance function
//int numbs[N]; // numbs[k] is the number of nodes i with d[i]==k
//
//// Reverse breadth-first search
//// to establish distance function d
//int rev_BFS() {
// int i, j, head(0), tail(0);
//
// // Initially, all d[i]=n
// for(i = 1; i <= n; i++)
// numbs[ d[i] = n ] ++;
//
// // Start from the sink
// numbs[n]--;
// d[sink] = 0;
// numbs[0]++;
//
// queue[ ++tail ] = sink;
//
// // While queue is not empty
// while( head != tail ) {
// i = queue[++head]; // Get the next node
//
// // Check all adjacent nodes
// for(j = 1; j <= n; j++) {
//
// // If it was reached before or there is no edge
// // then continue
// if(d[j] < n || G[j][i] == 0) continue;
//
// // j is reached first time
// // put it into queue
// queue[ ++tail ] = j;
//
// // Update distance function
// numbs[n]--;
// d[j] = d[i] + 1;
// numbs[d[j]]++;
//
// }
// }
//
// return 0;
//}
//
//// Augmenting the flow using predecessor list pi[]
//int Augment() {
// int i, j, tmp, width(oo);
//
// // Find the capacity of the path
// for(i = sink, j = pi[i]; i != source; i = j, j = pi[j]) {
// tmp = G[j][i];
// if(tmp < width) width = tmp;
// }
//
// // Augmentation itself
// for(i = sink, j = pi[i]; i != source; i = j, j = pi[j]) {
// G[j][i] -= width; F[j][i] += width;
// G[i][j] += width; F[i][j] -= width;
// }
//
// return width;
//}
//
//// Relabel and backtrack
//int Retreat(int &i) {
// int tmp;
// int j, mind(n-1);
//
// // Check all adjacent edges
// // to find nearest
// for(j=1; j <= n; j++)
// // If there is an arc
// // and j is "nearer"
// if(G[i][j] > 0 && d[j] < mind)
// mind = d[j];
//
// tmp = d[i]; // Save previous distance
//
// // Relabel procedure itself
// numbs[d[i]]--;
// d[i] = 1 + mind;
// numbs[d[i]]++;
//
// // Backtrack, if possible (i is not a local variable! )
// if( i != source ) i = pi[i];
//
// // If numbs[ tmp ] is zero, algorithm will stop
// return numbs[ tmp ];
//}
//
//
//// Main procedure
//int find_max_flow() {
// int flow(0), i, j;
//
// rev_BFS(); // Establish exact distance function
//
// // For each node current arc is the first arc
// for(i=1; i<=n; i++) CurrentNode[i] = 1;
//
// // Begin searching from the source
// i = source;
//
// // The main cycle (while the source is not "far" from the sink)
// for( ; d[source] < n ; ) {
//
// // Start searching an admissible arc from the current arc
// for(j = CurrentNode[i]; j <= n; j++)
// // If the arc exists in the residual network
// // and if it is an admissible
// if( G[i][j] > 0 && d[i] == d[j] + 1 )
// // Then finish searhing
// break;
//
// // If the admissible arc is found
// if( j <= n ) {
// CurrentNode[i] = j; // Mark the arc as "current"
// pi[j] = i; // j is reachable from i
// i = j; // Go forward
//
// // If we found an augmenting path
// if( i == sink ) {
// flow += Augment(); // Augment the flow
// i = source; // Begin from the source again
// }
// }
// // If no an admissible arc found
// else {
// CurrentNode[i] = 1; // Current arc is the first arc again
//
// // If numbs[ d[i] ] == 0 then the flow is the maximal
// if( Retreat(i) == 0 )
// break;
//
// }
//
// } // End of the main cycle
//
// // We return flow value
// return flow;
//}

    // from: http://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/

    static boolean bfs(int rGraph[][], int s, int t, int parent[])
        {
            // Create a visited array and mark all vertices as not
            // visited
            int V = rGraph.length;
            boolean visited[] = new boolean[V];
            for(int i=0; i<V; ++i)
                visited[i]=false;

            // Create a queue, enqueue source vertex and mark
            // source vertex as visited
            LinkedList<Integer> queue = new LinkedList<Integer>();
            queue.add(s);
            visited[s] = true;
            parent[s]=-1;

            // Standard BFS Loop
            while (queue.size()!=0)
            {
                int u = queue.poll();

                for (int v=0; v<V; v++)
                {
                    if (visited[v]==false && rGraph[u][v] > 0)
                    {
                        queue.add(v);
                        parent[v] = u;
                        visited[v] = true;
                    }
                }
            }

            // If we reached sink in BFS starting from source, then
            // return true, else false
            return (visited[t] == true);
        }

        // Returns tne maximum flow from s to t in the given graph
        static int fordFulkerson(int rGraph[][], int s, int t)
        {
            int u, v;

            int V = rGraph.length;

            // Create a residual graph and fill the residual graph
            // with given capacities in the original graph as
            // residual capacities in residual graph

            // Residual graph where rGraph[i][j] indicates
            // residual capacity of edge from i to j (if there
            // is an edge. If rGraph[i][j] is 0, then there is
            // not)
//            int rGraph[][] = new int[V][V];

//            for (u = 0; u < V; u++)
//                for (v = 0; v < V; v++)
//                    rGraph[u][v] = graph[u][v];

            // This array is filled by BFS and to store path
            int parent[] = new int[V];

            int max_flow = 0;  // There is no flow initially

            // Augment the flow while tere is path from source
            // to sink
            while (bfs(rGraph, s, t, parent))
            {
                // Find minimum residual capacity of the edhes
                // along the path filled by BFS. Or we can say
                // find the maximum flow through the path found.
                int path_flow = Integer.MAX_VALUE;
                for (v=t; v!=s; v=parent[v])
                {
                    u = parent[v];
                    path_flow = Math.min(path_flow, rGraph[u][v]);
                }

                // update residual capacities of the edges and
                // reverse edges along the path
                for (v=t; v != s; v=parent[v])
                {
                    u = parent[v];
                    rGraph[u][v] -= path_flow;
                    rGraph[v][u] += path_flow;
                }

                // Add path flow to overall flow
                max_flow += path_flow;
            }

            // Return the overall flow
            return max_flow;
        }

    public static class Graph {

        int[][] graph;
        int source;
        int sink;

        public Graph(int[][] graph, int source, int sink) {

        }

    }

    public static void main(String[] args) throws IOException {
        IN in = new IN();
        int n = in.getInt();// zadania
        int m = in.getInt();// procki
        if (n<=m) {
            System.out.println("TAK");
            return;
        }
        int[] p = new int[n];
        int[] k = new int[n];
        int[] c = new int[n];
        int mint = 0;
        int maxt = 0;
        int allTasksTime = 0;
        for (int i=0;i<n;i++) {
            p[i] = in.getInt();
            k[i] = in.getInt();
            c[i] = in.getInt();
            if (k[i]>maxt) maxt = k[i];
            allTasksTime += c[i];
        }

        int[][] G = new int[maxt + n + 3][maxt + n + 3];
        int zad = maxt +1;
        int source = zad + n;
        int sink = source + 1;

        for (int i=0;i<=maxt; i++) {
            G[source][i] = m;
        }
        for (int i=0;i<n;i++) {
            for (int j=p[i];j<k[i];j++) {
                G[j][zad + i] = 1;
            }
            G[zad + i][sink] = c[i];
        }

        int flow = fordFulkerson(G, source, sink);
        String resp = "";
        if (flow == allTasksTime) {
            resp = "TAK";
        } else {
            resp = "NIE";
        }
        System.out.println(resp);
    }
}