样例文件

题目描述

小明有 $k$ 个背包，其中第 $i$ 个背包里装着 $c_i$ 件物品。每件物品有一个价值，其中第 $i$ 个背包里的第 $j$ 件物品的价值为 $a_{i, j}$。

他准备从每个背包中恰好拿出一件物品，一共得到 $k$ 件物品的组合。他希望这 $k$ 件物品的总价值（价值之和）尽量大。请你告诉他在所有可能的物品组合里，总价值最大的 $n$ 个组合的总价值依次是多少?

输入格式

第一行：两个整数 $k, n$。

接下来 $k$ 行，每行描述一个背包中的物品信息，其中第 $i$ 行的第一个整数表示 $c_i$，接下来该行会有 $c_i$ 个整数，其中第 $j (1 ≤ j ≤ c_i)$ 个整数表示这个背包里第 $j$ 件物品的价值 $a_{i, j}$。

输出格式

一行，包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 大的总价值。数与数之间用一个空格隔开。

样例输入

2 4
2 1 2
3 3 2 1

样例输出

5 4 4 3

样例解释

小明共有 2 × 3 = 6 种取法，得到 6 种物品组合，总价值分别为 1 + 3 = 4, 1 + 2 = 3, 1 + 1 = 2, 2 + 3 = 5, 2 + 2 = 4, 2 + 1 = 3。

其中前 4 大的总价值依次为：5, 4, 4, 3

数据范围

$1 ≤ n ≤ \prod\limits_{i = 1}^{k}{c_i}, c_i ≥ 1, 1 ≤ a_{i, j} ≤ 10^9 (1 ≤ i ≤ k, 1 ≤ j ≤ c_i)。$