#6254. 最优卡组

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tangjz

题目描述

chitanda k 个卡包,第 i 个卡包里有 c_i 张卡,每张卡有一个能力值,其中第 i 个卡包里的第 j 张卡具有 a_{i, j} 点能力值。

他准备选择 k 张卡牌的组合,其中每个卡包要选择恰好一张卡牌。他希望这 k 张卡牌的能力值之和尽量大,请你告诉他在所有可能的组合里,能力值之和最大的 n 个组合分别具有多大的能力值。

输入格式

第一行包含两个整数 k n ,含义见题目描述。

接下来 k 行,每行描述一个卡包的信息,其中第 i 行的第一个整数表示 c_i ,接下来该行会有 c_i 个整数,依次表示这个卡包里每张卡的能力值。

输出格式

输出一行,包含 n 个整数,相邻两个数字之间用空格隔开,其中第 i 个整数表示第 i 大的能力值之和。

样例

样例输入

2 9
3 1 3 5
3 2 3 3

样例输出

8 8 7 6 6 5 4 4 3

样例解释

chitanda 3 \times 3 种选法,能力值分别为 1 + 2, 1 + 3, 1 + 3, 3 + 2, 3 + 3, 3 + 3, 5 + 2, 5 + 3, 5 + 3

数据范围与提示

对于所有数据, k \geq 2, 1 \leq n \leq \prod\limits_{i = 1}^{k}{c_i}, c_i \geq 1, 1 \leq a_{i, j} \leq 10^9 (i = 1, 2, \cdots, k; j = 1, 2, \cdots, c_i)

Subtask # 分值 k 的限制 n 的限制 \sum\limits_{i = 1}^{k}{c_i} 的限制
1 15 k = 2 n \leq 3 \times 10^5 \sum\limits_{i = 1}^{k}{c_i} \leq 3 \times 10^5
2 k \leq 10 n \leq 10^5 \sum\limits_{i = 1}^{k}{c_i} \leq 10^5
3 20 k \leq 500
4 50 k \leq 10^5 n \leq 3 \times 10^5 \sum\limits_{i = 1}^{k}{c_i} \leq 3 \times 10^5