#6254. 最优卡组

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

题目描述

chitandakk 个卡包,第 ii 个卡包里有 cic_i 张卡,每张卡有一个能力值,其中第 ii 个卡包里的第 jj 张卡具有 ai,ja_{i, j} 点能力值。

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

输入格式

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

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

输出格式

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

样例

样例输入

2 9
3 1 3 5
3 2 3 3

样例输出

8 8 7 6 6 5 4 4 3

样例解释

chitanda3×33 \times 3 种选法,能力值分别为 1+2,1+3,1+3,3+2,3+3,3+3,5+2,5+3,5+31 + 2, 1 + 3, 1 + 3, 3 + 2, 3 + 3, 3 + 3, 5 + 2, 5 + 3, 5 + 3

数据范围与提示

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

Subtask # 分值 kk 的限制 nn 的限制 i=1kci\sum\limits_{i = 1}^{k}{c_i} 的限制
1 1515 k=2k = 2 n3×105n \leq 3 \times 10^5 i=1kci3×105\sum\limits_{i = 1}^{k}{c_i} \leq 3 \times 10^5
2 1515 k10k \leq 10 n105n \leq 10^5 i=1kci105\sum\limits_{i = 1}^{k}{c_i} \leq 10^5
3 2020 k500k \leq 500 n105n \leq 10^5 i=1kci105\sum\limits_{i = 1}^{k}{c_i} \leq 10^5
4 5050 k105k \leq 10^5 n3×105n \leq 3 \times 10^5 i=1kci3×105\sum\limits_{i = 1}^{k}{c_i} \leq 3 \times 10^5