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
121
122
123
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

const long long INF = (long long)1e18 + 1;

struct jelly_bean {
    int color;
	int weight;
	int price;

	bool operator<(const jelly_bean &a) const {
		return color < a.color;
	}
};

vector<long long> knapsack(vector<jelly_bean> items, int diff_colors, int m) {
    vector<vector<long long>>
		res(diff_colors + 1, vector<long long>(m, INF));
	res[0][0] = 0;

	int curr_color = 0;
	for (int i = 0; i < items.size(); i++) {
		if (items[i].color != items[i - 1].color) {
			curr_color++;
		}
		for (int j = 0; j < m; j++) {
			int subtracted = (j - items[i].weight) % m;
			if (subtracted < 0)
				subtracted += m;
			res[curr_color][j] = min(res[curr_color][j], res[curr_color - 1][subtracted]
					+ items[i].price);
		}
	}

	return res.back();
}

vector<long long> concat(vector<long long> one_color, int m) {
	vector<long long> potentially(one_color.size(), INF);
    for (int i = 0; i < (int)one_color.size(); i++) {
		if (one_color[i] != INF)
			potentially[i] = INF + 1;
	}
	for (int i = 0; i < (int)one_color.size(); i++) {
		for (int j = 0; j < (int)one_color.size(); j++) {
            int idx = (i + j) % m;
			long long sum = one_color[i] + one_color[j];
			if (potentially[idx] != -1 && potentially[idx] > sum)
				potentially[idx] = sum;
		}
	}

	while (true) {
		int min_idx = 0;
		for (int i = 0; i < (int)one_color.size(); i++) {
			if (potentially[i] < potentially[min_idx]) {
				min_idx = i;
			}
		}
		if (potentially[min_idx] == INF + 1)
			break;

		one_color[min_idx] = potentially[min_idx];
		potentially[min_idx] = INF + 1;

		int new_idx = min_idx;
		for (int i = 0; i < (int)one_color.size(); i++) {
			if (potentially[new_idx] != INF + 1 &&
					one_color[i] + one_color[min_idx] < potentially[new_idx]) {
                potentially[new_idx] = one_color[i] + one_color[min_idx];
			}

			new_idx++;
			if (new_idx >= m)
				new_idx -= m;
		}
	}

	return one_color;
}

int main() {
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
    int n, k, m;
	cin >> n >> k >> m;
    vector<jelly_bean> jelly_beans(n);

	unordered_set<int> colors;

	int n_i, k_i, m_i;
	for (int i = 0; i < n; i++) {
		cin >> n_i >> k_i >> m_i;
		jelly_beans[i] = {n_i, k_i, m_i};
		colors.insert(n_i);
	}
	if (colors.size() != k) {
		cout << "0\n";
		for (int i = 0; i < m - 1; i++) {
			cout << -1 << '\n';
		}
		return 0;
	}

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

    vector<long long> one_color = knapsack(jelly_beans, k, m);
	one_color[0] = 0;

	vector<long long> prices = concat(one_color, m);

	for (int i = 0; i < m; i++) {
		cout << (prices[i] != INF ? prices[i] : -1) << '\n';
	}

	return 0;
}