P2409 Y's Blocks

Y is a great architect. He can always build the most creative shapes with the simplest blocks.

Y has $n$ boxes of blocks, and each block has a weight. He wants to pick one block from each box and put them together; the total weight of this pile is the sum of the weights of the chosen blocks. Now he wants to know the weights of the $k$ selections with the smallest total weights. (As long as you replace any single block, it is considered a different selection. If multiple selections have the same total weight, we should output that weight multiple times.)

The first line contains two integers, $n,k$, as described. In the next $n$ lines, line $i$ starts with an integer $m_i$, the number of blocks in the $i$-th box. On the same line, there are $m_i$ integers, which are the weights of the blocks.

Output one line containing the weights of the $k$ selections with the smallest total weights, in nondecreasing order.

Constraints - For $30\%$ of the testdata, $2 \le m_i \le 10$, $1 \le n \le 10$. - For $50\%$ of the testdata, $2 \le m_i \le 50$, $1 \le n \le 50$. - For $100\%$ of the testdata, $2 \le m_i \le 100$, $1 \le n \le 100$, $1 \le k \le 10^4$, each block’s weight is a positive integer not exceeding $100$, and the product of all $m_i$ is at least $k$. This problem does not stress constant factors. Translated by ChatGPT 5