Description

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.)

Input Format

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 Format

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

3 10
4 1 3 4 5
3 1 7 9
4 1 2 3 5

3 4 5 5 6 6 7 7 7 7

Hint

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