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
//
//  main.cpp
//  zel
//
//  Created by Michal Kowalski on 14/03/2024.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void generate_sets(int depth, vector<int> v);
void find_solution();
void calc_price(vector<int> &t);
void print_solution();
long long calculate_last_sum();

int N,K,M;
vector<vector<int> > T(7005);
vector<vector<int> > COL(7005);
vector<vector<int> > COMB;
int TABM[7005];

long long last_sum = (long long)7005*INT32_MAX;

int main() {
    for (int i=0;i<7005;++i) TABM[i]=INT32_MAX;

    scanf("%d %d %d",&N,&K,&M);
    for (int i=0;i<N;++i) {
        int k,w,p;
        scanf("%d %d %d",&k,&w,&p);
        T[i] = {k,w,p};
        COL[k].push_back(i);
    }
    generate_sets(0, {});
    if (COMB.empty()) {
        TABM[0]=0;
        print_solution();
        return 0;
    }


    find_solution();

    print_solution();
    return 0;
}


void generate_sets(int depth, vector<int> v) {
    if (depth == K) {
        COMB.push_back(v);
    } else {
        for(auto c: COL[depth+1]) {
            vector<int> t  = v;
            t.push_back(c);
            generate_sets(depth+1, t);
        }
    }
}


void find_solution() {
    queue<vector<int>> Q;
    Q.push({});
    int step = 1;
    bool finish = false;
    while(!finish) {
        vector<int> t = Q.front();
        Q.pop();
        calc_price(t);

        for (auto com: COMB) {
            vector<int> nt = t;
            // add
            for (auto x: com) nt.push_back(x);
            Q.push(nt);
        }
        ++step;

        /// check if output array changed if not finish
        if (step % 5000 == 0) {
            long long currentSum = calculate_last_sum();
            if (currentSum == last_sum) {
                finish = true;
            } else {
                last_sum = currentSum;
            }
        }
    }
}

void calc_price(vector<int> &t) {
    int price = 0;
    int weight = 0;
    for(auto index: t) {
        price += T[index][2];
        weight += T[index][1];
    }
    int mindex = weight%M;
    TABM[mindex] = min(TABM[mindex], price);
}


void print_solution() {
    for(int i=0;i<M;++i) {
        printf("%d\n",TABM[i] == INT32_MAX ? -1 : TABM[i]);
    }
}

long long calculate_last_sum() {
    long long current = 0;
    for(int i=0;i<M;++i) {
        current = current + (long long) TABM[i];
    }
    return current;
}