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

#define INF (long long)(1e18)

using namespace std;
using ll = long long;

struct jelly {
    int k;
    long long m;
    int c;

    bool operator<(const jelly& o) {
        return k < o.k;
    }
};

int N, K;
ll M;
vector<jelly> jellies;

ll dp[7005][7005];
bool exist[7005];
ll cost[7005];

void find_rest(){
    vector<int> rest;
    for (int i = 0; i < M; i++) {
        if(dp[K][i] != INF){
            rest.push_back(i);
            exist[i] = 1;
            cost[i] = dp[K][i];
        }else{
            cost[i] = INF;
        }
    }
    cost[0]=0;

    bool changer = true;
    while(changer){
        changer = false;
        int basic_size = rest.size();
        for(int i = 0;i<basic_size;i++)
            for(int j = 0;j<basic_size;j++){
                int new_rest = (rest[i] + rest[j])%M;
                if(!exist[new_rest]){
                    rest.push_back(new_rest);
                    changer = true;
                    exist[new_rest] = 1;
                }
                else if(cost[rest[i]]+cost[rest[j]] < cost[new_rest])
                    changer = true;
                cost[new_rest] = min(cost[new_rest],cost[rest[i]]+cost[rest[j]]);
            }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> N >> K >> M;
    for (int i = 0; i < N; i++) {
        int k, m, c;
        cin >> k >> m >> c;
        jellies.push_back({k,m,c});
    }

    sort(jellies.begin(), jellies.end());

    for (int i = 0; i <= K; i++)
        for (int j = 0; j <= M; j++)
            dp[i][j] = INF;
    dp[0][0]=0;

    int prev_k = -1;
    int cur_k = 0;
    for (auto jelly : jellies) {
        if (jelly.k != prev_k) {
            cur_k++;
            prev_k = jelly.k;
        }
        for (int r = 0; r < M; r++) {
            int new_r = (r+jelly.m)%M;

            dp[cur_k][new_r] = min(dp[cur_k][new_r], dp[cur_k-1][r]+jelly.c);
        }

    }

    find_rest();

    for(int i =0 ;i<M;i++){
        if(cost[i] == INF)cost[i]=-1;
        cout << cost[i]<<"\n";
    }

    return 0;
}