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
import sys
n, k, m = [int(x) for x in input().split()]
# TODO: is this higher than max?
MAX_RES = 1_000_000_000_000_000
# [jelly type, number of jellies, mass modulo m] -> lowest cost
cheapest = [[[MAX_RES for _ in range(m)] for _ in range(m + 1)] for _ in range(k)]

for ki in range(k):
    cheapest[ki][0][0] = 0

for _ in range(n):
    ki, mi, ci = [int(x) for x in input().split()]
    for number in range(1, m + 1):
        for mass in range(0, m):
            cheapest[ki - 1][number][(mass + mi) % m] = min(cheapest[ki - 1][number][(mass + mi) % m], ci + cheapest[ki - 1][number - 1][mass])

for ki in range(k):
#    print("jellies type", ki + 1, file=sys.stderr)
    for num in range(1, m + 1):
#        print("if I were to use ", num, "of them", file=sys.stderr)

        for r in range(m):
            if cheapest[ki][num][r] != MAX_RES:
                pass
#                print("to create rest", r, "it would cost", cheapest[ki][num][r], file=sys.stderr)

def lowest_cost(number):
    costs = [0] + [MAX_RES for _ in range(m - 1)]
    for ki in range(k):
        new_costs = [MAX_RES for _ in range(m)]
#        print("for number", number, "up until jellies", ki + 1, file=sys.stderr)
        for jelly_mass in range(0, m):
            if cheapest[ki][number][jelly_mass] == MAX_RES:
                continue
            for prev_mass in range(0, m):
                if costs[prev_mass] == MAX_RES:
                    continue
#                print("for prev_mass", prev_mass, "and jelly mass", jelly_mass)
                new_costs[(prev_mass + jelly_mass) % m] = min(
                    new_costs[(prev_mass + jelly_mass) % m],
                    cheapest[ki][number][jelly_mass] + costs[prev_mass])
#        print("the costs are", new_costs)

        costs = new_costs

    return costs  # r -> lowest cost for producing jellies of mass r % m with number of jellies of each type

res = [MAX_RES for _ in range(m)]
for num in range(m + 1):  # you need at most m jellies of each type
    current_lowest = lowest_cost(num)
    for i in range(m):
        res[i] = min(res[i], current_lowest[i])

for i in range(m):
    if res[i] != MAX_RES:
        print(res[i])
    else:
        print(-1)