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
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN = 7e3+7;
int color[MAXN], mass[MAXN], price[MAXN];
ll res[MAXN];
vector<int> colors[MAXN];
int main()
{
	ios_base::sync_with_stdio(0);
    int n,k,m; cin>>n>>k>>m;
    for(int i=1;i<=n;++i) cin>>color[i]>>mass[i]>>price[i];
    for(int i=1;i<=n;++i) colors[color[i]].pb(i);
    for(int i=1;i<m;++i) res[i] = INFLL;
    vector<ll> dp(m, INFLL);
    dp[0] = 0;
    for(int j=1;j<=k;++j){
        vector<ll> color_dp(m, INFLL);
        for(int &v:colors[j]){
            int pr = price[v], ms = mass[v]%m;
            for(int l=0;l<m;++l){
                int tmp = l-ms;
                if(tmp < 0) tmp += m;
                color_dp[l] = min(color_dp[l], dp[tmp]+pr);
            }
        }
        swap(dp, color_dp);
    }
    for(int i=1;i<m;++i){
        int curr = 0;
        ll tmp = 0;
        for(int j=1;j<m;++j){
            curr += i;
            if(curr >= m) curr -= m;
            tmp = min(tmp + dp[i], INFLL);
            if(dp[i] != INFLL) dp[curr] = min(dp[curr], tmp);
        }
    }
    vector<pil> items;
    for(int i=1;i<m;++i) if(dp[i] != INFLL) items.pb({i, dp[i]});
    vector<ll> dp2(m*2, INFLL);
    dp2[0] = 0;
    for(pil &p:items){
        int r = p.first; ll pr = p.second;
        for(int i=r;i<m*2;++i){
            dp2[i] = min(dp2[i], dp2[i-r]+pr);
        }
        for(int i=0;i<m;++i) dp2[i] = min(dp2[i], dp2[i+m]);
    }
    for(int i=0;i<m;++i){
        if(dp2[i] == INFLL) cout<<"-1\n";
        else cout<<dp2[i]<<"\n";
    }
}