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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 7007;
const long long INF = 1337133713371337133;

vector<pair<int, long long>> zelki[N];
long long _dp[2][N];


int main() {
    int n, k, m, ki, mi;
    long long ci;
    scanf("%d%d%d", &n, &k, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%lld", &ki, &mi, &ci);
        zelki[ki].emplace_back(mi, ci);
    }

    auto dp = _dp[0], prevdp = _dp[1];

    for (int i = 0; i < m; i++) {
        dp[i] = INF;
    }

    dp[0] = 0;
    for (int kolor = 1; kolor <= k; kolor++) {
        swap(dp, prevdp);
        for (int r = m - 1; r >= 0; r--) {
            long long newdpr = INF;
            for (auto z: zelki[kolor]) {
                newdpr = min(prevdp[(r + m - z.first) % m] + z.second, newdpr);
            }
            dp[r] = newdpr;
        }
    }

    for (int r = m / 3; r < m; r++) {
        prevdp[r] = dp[r];
    }
    for (int r = m / 3; r < m; r++) {
        if (prevdp[r] < INF) {
            int newr = r, pow = 1;
            for (int i = 1; i < 5; i++) {
                pow *= 2;
                newr = (newr * 2) % m;
                dp[newr] = min(dp[newr], prevdp[r] * pow);
            }
        }
    }

    dp[0] = 0;
    bool stop = false;

    for (int i = 0; !stop && i < 13; i++) {
        stop = true;
        for (int r = 0; r < m; r++) {
            for (int w = 0; w < m; w++) {
                if (dp[r] + dp[w] < dp[(r + w) % m]) {
                    stop = false;
                    dp[(r + w) % m] = dp[r] + dp[w];
                }
            }
        }
    }

    for (int r = 0; r < m; r++) {
        printf("%lld\n", (dp[r] < INF ? dp[r] : -1));
    }
    return 0;
}