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

#define int long long

typedef pair<int, int> PII;

constexpr int M = 7e3+7;
constexpr int inf = 1e18;

int n, k, m;

vector<PII> zelek[M];

int dp[M][M];//dp[i][j]-koszt uzyskania multizbioru z reszta j, przy czym i to ile jest zelkow kazdego koloru

void init(){
	for(int i=0; i<=m; i++){
		for(int j=0; j<=m; j++){
			dp[i][j] = inf;
		}
	}
	dp[0][0] = 0;
}

void update(int i, int j){
	for(int tmp=0; tmp<m; tmp++){
		int act = tmp+j;
		if(act >= m) act -= m;
		dp[i][act] = min(dp[i][act], dp[i-1][tmp]+dp[1][j]);
	}
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> k >> m;
	
	init();
	
	for(int i=1; i<=n; i++){
		int ak, am, ac;
		cin >> ak >> am >> ac;
		zelek[ak].push_back({am,ac});
	}
	
	//liczenie jak zrobic dp[1][reszta] - O(n^2)
	vector<int> before(m,inf), act(m,inf);
	before[0] = 0;
	for(int i=1; i<=k; i++){
		for(auto j : zelek[i]){
			int masa = j.first, cena = j.second;
			for(int l=0; l<m; l++){
				act[(l+masa)%m] = min(act[(l+masa)%m], before[l]+cena);
			}
		}
		swap(before, act);
		fill(act.begin(), act.end(), inf); 
	}		
	
	for(int i=0; i<m; i++) dp[1][i] = before[i];
	
	int st = 5e8 / (m*m);
	
	for(int i=2; i<=min(m,st); i++){
		for(int j=0; j<m; j++){
			update(i,j);
		}
	}
	
	cout << 0 << '\n';
	for(int j=1; j<m; j++){
		int res = inf;
		for(int i=1; i<=m; i++){
			res = min(res, dp[i][j]);
		}
		if(res == inf) cout << -1 << '\n';
		else cout << res << '\n';
	}
	
	return 0;
}