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

using namespace std;

typedef long long LL;
const LL Q=10000000LL*1000000000;

int main()
{
    ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, k, m;
    cin>>n>>k>>m;
    vector<pair<int, int>> x[7001];//[kolor]<masa, cena>
    for (int i=0; i<n; ++i)
    {
        int kk, mm, cc;
        cin>>kk>>mm>>cc;
        x[kk].push_back(make_pair(mm, cc));
    }

    for (int i=1; i<=k; ++i)
        if (x[i].empty())
        {
            cout<<0<<'\n';
            for (int j=1; j<m; ++j)
                cout<<"-1\n";
            return 0;
        }

    vector<LL> wyn;
    wyn.push_back(0);
    for (int i=1; i<m; ++i)
        wyn.push_back(Q);

    vector<LL> wd(wyn);

    for (int mm=0; mm<m; ++mm)
    {
        for (int kk=1; kk<=k; ++kk)
        {
            vector<LL> wn;
            for (int i=0; i<m; ++i)
                wn.push_back(Q);

            for (auto &a : x[kk])
            {
                for (int i=0; i<m; ++i)
                    if (wd[i]!=Q)
                    {
                        int z=i+a.first;
                        if (m<=z)
                            z-=m;
                        wn[z]=min(wn[z], wd[i]+a.second);
                    }
            }
            wd.swap(wn);
        }

        bool byl=false;
        for (int i=0; i<m; ++i)
            if (wd[i]<wyn[i])
            {
                byl=true;
                wyn[i]=wd[i];
            }
        if (!byl)
            break;
    }

    for (int i=0; i<m; ++i)
        cout<<(wyn[i]==Q ? -1 : wyn[i])<<'\n';
    return 0;
}