Background

PA 2024 3B

Problem Description

This problem is translated from PA 2024 Round 3 Żelki. Thanks to Macaronlin for providing the translation.

There are $n$ types of jelly beans and $k$ colors. The $i$-th type has color $k_i$, weight $m_i$, and price $c_i$. Now you want to buy jelly beans. The jelly beans you buy must include all $k$ colors, and the number bought for each color must be the same.

For each integer $r$ in the interval $[0,m-1]$, find the minimum total cost among all buying plans whose total weight modulo $m$ equals $r$. If no plan satisfies the conditions, output $-1$.

Input Format

The first line contains three integers $n,k$ and $m\ (1\le n,k,m\le 7\,000)$, representing the number of jelly bean types, the number of colors, and the parameter.

The next $n$ lines each contain three integers $k_i,m_i$ and $c_i\ (1\le k_i\le k,1\le m_i\le m,1\le c_i\le 10^9)$, representing the color, weight, and price of the $i$-th type.

Output Format

Output $m$ lines. The $i$-th line should be the minimum cost among all cases where the total weight of all bought jelly beans modulo $m$ is $i-1$. If no such case exists, output $-1$.

3 2 6
1 2 1
2 2 2
1 1 5

0
10
6
7
3
13

2 3 3
1 1 1
3 1 1

0
-1
-1

Hint

In the first sample:

• To make the total weight divisible by $m = 6$, you can buy no jelly beans, so you do not need to pay anything.
• To make the remainder of the total weight divided by $6$ equal to $1$, you should buy one jelly bean of the first type, two of the second type, and one of the third type. The cost is $10$, and you get two colors with two jelly beans each, with total weight $7$.
• To make the remainder of the total weight divided by $6$ equal to $5$, you should buy two jelly beans of the first type, three of the second type, and one of the third type.

In the second sample, there are no jelly beans of the second color, so the only feasible plan is to buy no jelly beans.

Translated by ChatGPT 5