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
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9+7;

namespace Flow {
    struct edge {
        int to, rev, cap, flow;
    };

    const int N = 1005;
    int n, dst[N], pos[N];
    vector<edge> g[N];

    void add(int a, int b, int c) {
        g[a].push_back({b, (int)g[b].size(), c, 0});
        g[b].push_back({a, (int)g[a].size() - 1, 0, 0});
    }

    int dfs(int f, int s, int cost = inf) {
        if (f == s) return cost;
        if (!cost) return 0;
        for (int &i = pos[f]; i < (int)g[f].size(); ++i) {
            auto &item = g[f][i];
            if (dst[item.to] == dst[f] + 1) {
                int val = dfs(item.to, s, min(cost, item.cap - item.flow));
                if (val > 0) {
                    item.flow += val;
                    g[item.to][item.rev].flow -= val;
                    return val;
                }
            }
        }
        return 0;
    }

    bool bfs(int f, int s) {
        fill(dst, dst + n, inf);
        dst[f] = 0;
        queue<int> q;
        q.push(f);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto& item : g[v]) {
                if (dst[item.to] > dst[v] + 1 && item.cap > item.flow) {
                    dst[item.to] = dst[v] + 1;
                    q.push(item.to);
                }
            }
        }
        return dst[s] < inf;
    }

    int maxFlow(int f, int s) {
        int result = 0, val;
        while (true) {
            if (!bfs(f, s)) 
                break;
            fill(pos, pos + n, 0);
            while ((val = dfs(f, s)) > 0) 
                result += val;
        }
        return result;
    }
};

const int N = 105;
const int M = 1000005;

int n, m, l[N], r[N], c[N];
int bal[M], st[M], ed[M];

void solve() {
    cin >> n >> m;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> l[i] >> r[i] >> c[i];
        sum += c[i];
        --r[i];
        st[l[i]] = 1;
        ed[r[i]] = 1;
    }
    vector<pair<int,int>> seg;
    for (int i = 0; i <= 1000001; ++i) {
        int j = i;
        while (j <= 1000001 && !(st[j+1] || ed[j])) ++j;
        seg.emplace_back(i, j);
        i = j;
    }
    Flow::n = 2 + n + (int)seg.size();
    for (int i = 0; i < n; ++i) {
        Flow::add(0, i + 1, c[i]);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (int)seg.size(); ++j) {
            auto item = seg[j];
            if (l[i] <= item.first && r[i] >= item.second) {
                Flow::add(i + 1, j + n + 1, (item.second-item.first+1));
            }
        }
    }
    for (int j = 0; j < (int)seg.size(); ++j) {
        auto item = seg[j];
        Flow::add(j + n + 1, Flow::n - 1, (item.second-item.first+1)*m);
    }
    int val = Flow::maxFlow(0, Flow::n - 1);
    if (val == sum) {
        cout << "TAK\n";
    } else {
        cout << "NIE\n";
    }
}

int main() {
    ios::sync_with_stdio(false);

    int z = 1;
    while (z--) solve();
    return 0;
}