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

using namespace std;

struct pending_task {
    int needed_time;
    int end_before;

    inline bool operator<(const pending_task& other) const {
        return (end_before - needed_time) < (other.end_before - other.needed_time);
    }
};

struct running_task {
    int started_time;
    int needed_time;
    int end_before;
};

void no() {
    cout << "NIE" << endl;
    exit(0);
}

template <typename T>
inline void choose_first_n(vector<T>& v, int n) {
    if (n >= v.size()) {
        return;
    }

    auto nth = v.begin() + n;
    nth_element(v.begin(), nth, v.end());

    auto next = nth + 1;
    while (next != v.end() && *nth < *next) next++;

    for (auto it = v.begin(); it != nth; it++) {
        if (*nth < *it) {
            swap(*it, *next);
            next++;
            while (next != v.end() && *nth < *next) next++;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pending_task>> pending_tasks(1000001);

    for (int i = 0; i < n; i++) {
        int p, k, c;
        cin >> p >> k >> c;

        pending_task pt = { c, k };
        pending_tasks[p].push_back(pt);
    }

    vector<pending_task> waiting_tasks;
    vector<running_task> running_tasks;

    waiting_tasks.reserve(105);
    running_tasks.reserve(105);

    for (int cur_second = 0; cur_second <= 1000000; cur_second++) {
        for (const auto& rt: running_tasks) {
            if (rt.started_time + rt.needed_time > cur_second) {
                pending_task pt = { rt.needed_time - (cur_second - rt.started_time), rt.end_before };
                waiting_tasks.push_back(pt);
            }
        }

        running_tasks.clear();

        for (const auto& pt: pending_tasks[cur_second]) {
            waiting_tasks.push_back(pt);
        }

        choose_first_n(waiting_tasks, m);

        for (int i = 0, mn = min(m, int(waiting_tasks.size())); i < mn; i++) {
            const pending_task& pt = waiting_tasks[i];
            if (cur_second + pt.needed_time > pt.end_before) {
                no();
            }

            running_task rt = { cur_second, pt.needed_time, pt.end_before };
            running_tasks.push_back(rt);
        }

        if (int(waiting_tasks.size()) <= m) {
            waiting_tasks.clear();
        } else {
            for (int i = 0; i < m; i++) {
                swap(waiting_tasks[i], waiting_tasks[waiting_tasks.size() - 1 - i]);
            }
            
            waiting_tasks.resize(max(0, int(waiting_tasks.size()) - m));
        }
    }

    if (waiting_tasks.size()) {
        no();
    }

    cout << "TAK" << endl;
}