#P2409. Y的积木

Y的积木

题目背景

Y 是个大建筑师,他总能用最简单的积木拼出最有创意的造型。

题目描述

Y 手上有 nn 盒积木,每个积木有个重量。现在他想从每盒积木中拿一块积木,放在一起,这一堆积木的重量为每块积木的重量和。现在他想知道重量和最小的 kk 种取法的重量分别是多少。(只要任意更换一块积木,就视为一种不同的取法。如果多种取法重量总和一样,我们需要输出多次。)

输入格式

第一行输入两个整数,n,kn,k,意义如题目所描述。

每组数据接下来的 nn 行,第一个整数为 mim_i,表示第 ii 盒积木的数量,在同一行有 mim_i 个整数,分别表示每个积木的重量。

输出格式

一行,重量最小的 kk 种取法的重量,要求对于每个数据,从小到大输出。

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

提示

数据规模与约定

  • 对于 30%30\% 的数据,2mi102 \le m_i \le 101n101 \le n \le 10
  • 对于 50%50\% 的数据,2mi502 \le m_i \le 501n501 \le n \le 50
  • 对于 100%100\% 的数据,2mi1002 \le m_i \le 1001n1001 \le n \le 1001k1041 \le k \le 10^4,每个积木的重量为不超过 100100 的正整数,所有 mim_i 的积大于等于 kk

本题不卡常。