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
from collections import defaultdict, namedtuple
from itertools import combinations_with_replacement, product
import numpy as np

INF = int(1e10)
MAX_COLOR_PICK = 4

n, k, m = map(int, input().split())

color_bucket = defaultdict(list)

cost = np.array([INF for _ in range(m)])

Rodzaj = namedtuple('Rodzaj', ['mass', 'price'])

for i in range(n):
    k_i, m_i, c_i = map(int, input().split())
    color_bucket[k_i].append(Rodzaj(m_i, c_i))

if len(color_bucket) != k:
    print(0)
    for i in range(1, m):
        print(-1)
    exit(0)

for i in range(1, MAX_COLOR_PICK):
    bucket_combinations = []
    for j in range(1, k+1):
        bucket_combinations.append(
            list(combinations_with_replacement(color_bucket[j], i)))

    product_of_combinations = list(product(*bucket_combinations))

    for prod_ele in product_of_combinations:
        sum_mass = 0
        price = 0

        for bucket in prod_ele:
            for jelly in bucket:
                sum_mass += jelly.mass
                price += jelly.price

        if cost[sum_mass % m] > price:
            cost[sum_mass % m] = price

print(0)
for i in range(1, m):
    if cost[i] == INF:
        print(-1)
    else:
        print(cost[i])