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

#define MX 1000006

#define MP(a,b) make_pair(a,b)
#define PB(a) push_back(a)

using namespace std;

int P[102],K[102],C[102],T[202];//,S[102],KP[102];
vector<int> PP[MX],KK[MX];

bool sort_func( int i, int j ) {
    return K[i]-C[i]<K[j]-C[j];
}

int main() {
    int n,m,mx=0;
    scanf("%d%d",&n,&m);
    for ( int i=0; i<n; i++ ) {
        int p,k,c;
        scanf("%d%d%d",&p,&k,&c);
        P[i]=-1; K[i]=k; C[i]=c;// KP[i]=;
        mx=max( mx, K[i] );
        PP[p].PB(i);
        KK[k-1].PB(i);
    }
    int r = 0;
    int l=0;
    int nt=0;
    for ( int i=0; i<=mx; i++ ) {
        for ( int j=0; j<PP[i].size(); j++ ) T[ nt++ ] = PP[i][j];
        sort(T,T+nt,sort_func);
        for ( int j=0; j<min(m,nt); j++ ) {
            int v = T[j];
            if (!(--C[v])) {
                KK[i].PB(v);
            }
        }
        for ( int j=0; j<KK[i].size(); j++ ) {
            int vv=KK[i][j];
            for ( int v=0; v<nt; v++ )
                if ( T[v]==vv ) {
                    T[v]=T[--nt];
                    break;
                }
        }
    }
    /*{ 
        vector<int> &pp = PP[i];
        vector<int> &kk = KK[i];
        if ( !pp.size() && !kk.size() ) continue;
        l++;
        for ( int j=0; j<(int)pp.size(); j++ ) {
            int v = pp[j];
            if ( P[v]<0 && C[v] && K[v]>i ) {
                P[v] = i;
                KK[min(mx,i+C[v])].PB( v );
                r++;
            }
        }
        if ( r>m ) {
            for ( int v=0; v<n; v++ ) S[v]=0;
            for ( int j=0; j<r-m; j++ ) {
                int mm=0, mr=-1;
                for ( int v=0; v<n; v++ ) {
                    if ( !S[v] && P[v]!=-1 && K[v]-C[v]>mm ) {
                        mr=v; mm=K[v];
                    }
                }
                kk.PB(mr); S[mr]=1;
            }
        } else {
            for ( int v=0; v<n; v++ ) S[v]=0;
            int aa = m-r;
            for ( int j=0; j<aa; j++ ) { 
                int mm=MX, mr=-1;
                for ( int v=0; v<n; v++ ) {
                    if ( P[v]<0 && C[v] && K[v]-C[v]<mm && K[v]>i ) {
                        mr=v; mm=K[v];
                    }
                }
                if ( mr!=-1 ) {
                    int v = mr;
                    P[v] = i;
                    KK[min(mx,i+C[v])].PB( v );
                    r++;
                }
            }
        }
        for ( int j=0; j<(int)kk.size(); j++ ) {
            int v = kk[j];
            if ( P[v] >= 0 ) {
                C[v] -= i-P[v];
                P[v] = -1;
                r--;
            }
        }
    }
    printf("%d\n",l);//*/
    //for ( int i=0; i<n; i++ ) printf("%d ",C[i]); printf("\n");
    for ( int i=0; i<n; i++ ) if ( C[i]>0 ) {
        printf("NIE\n");
        return 0;
    }
    printf("TAK\n");
    return 0;
}