题目描述
chitanda
有 k 个卡包,第 i 个卡包里有 ci 张卡,每张卡有一个能力值,其中第 i 个卡包里的第 j 张卡具有 ai,j 点能力值。
他准备选择 k 张卡牌的组合,其中每个卡包要选择恰好一张卡牌。他希望这 k 张卡牌的能力值之和尽量大,请你告诉他在所有可能的组合里,能力值之和最大的 n 个组合分别具有多大的能力值。
输入格式
第一行包含两个整数 k 和 n,含义见题目描述。
接下来 k 行,每行描述一个卡包的信息,其中第 i 行的第一个整数表示 ci,接下来该行会有 ci 个整数,依次表示这个卡包里每张卡的能力值。
输出格式
输出一行,包含 n 个整数,相邻两个数字之间用空格隔开,其中第 i 个整数表示第 i 大的能力值之和。
2 9
3 1 3 5
3 2 3 3
8 8 7 6 6 5 4 4 3
数据范围与提示
对于所有数据,k≥2, 1≤n≤i=1∏kci, ci≥1, 1≤ai,j≤109 (i=1,2,⋯,k;j=1,2,⋯,ci)。
Subtask # |
分值 |
k 的限制 |
n 的限制 |
i=1∑kci 的限制 |
1 |
15 |
k=2 |
n≤3×105 |
i=1∑kci≤3×105 |
2 |
k≤10 |
n≤105 |
i=1∑kci≤105 |
3 |
20 |
k≤500 |
4 |
50 |
k≤105 |
n≤3×105 |
i=1∑kci≤3×105 |