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

using namespace std;

long long MAX = 1L<<61;

// inputs
int n, k, m;
// for every color list of <weight, price>
vector<pair<int, long long>> G[7010]; 

// A[i] shows minimal price for each of modulo using kolors from [1, .., i]
// i.e. A[i][j] shows minimal price to get j (mod m) using colors from [1, .., i] 
long long A[7010][7010];
// Combinations
// C[i] shows minimal price for each of modulo (for any number of gummies) after i rounds
long long C[7010][7010];

int main() {
	int color, weight, price;
	scanf("%d%d%d", &n, &k, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &color, &weight, &price);
		G[color].push_back(make_pair(weight, price));
	}

	for (int i = 0; i <= k; i++) {
		for (int j = 0; j <= m; j++) {
			A[i][j] = MAX;
		}
	}
	A[0][0] = 0;

	long long actual_price, new_price;
	int new_weight, new_modulo;

	for (int next_color = 1; next_color <= k; next_color++) {
		for (auto gummy_idx = G[next_color].begin(); gummy_idx != G[next_color].end(); gummy_idx++) {
			for (int modulo = 0; modulo < m; modulo++) {
				actual_price = A[next_color - 1][modulo];
				new_price = actual_price + gummy_idx->second;
				new_weight = (modulo + gummy_idx->first) % m;
				A[next_color][new_weight] = min(A[next_color][new_weight], new_price);
			}
		}
	}

	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= m; j++) {
			C[i][j] = MAX;
		}
	}
	C[0][0] = 0;

	for (int modulo = 0; modulo < m; modulo++) {
		C[1][modulo] = A[k][modulo];
	}

	C[1][0] = 0;

	// We need only m rounds, because if one round doesn't give new modulos, then we can stop.
	// If each round gives at least one new modulo, after max. m rounds we fill m-size table.
	int round = 2;
	for (; round <= m; round++) {
		for (int modulo = 0; modulo < m; modulo++) {
			C[round][modulo] = C[round - 1][modulo];
		}
		bool dirty = false;
		for (int prev_modulo = 0; prev_modulo < m; prev_modulo++) {
			for (int move_modulo = 0; move_modulo < m; move_modulo++) {
				actual_price = C[round - 1][prev_modulo];
				new_price = C[round - 1][prev_modulo] + C[round - 1][move_modulo];
				new_modulo = (prev_modulo + move_modulo) % m;
				if (C[round][new_modulo] > new_price) {
					dirty = true;
					C[round][new_modulo] = new_price;
				}
			}
		}
		if (!dirty) break;
	}

	for (int i = 0; i < m; i++) {
		if (C[round][i] == MAX) {
			printf("-1\n");
		} else {
			printf("%lld\n", C[round][i]);
		}
	}
}