分数: 1500 点
问题陈述
伊吕波有一系列 N 字符串 s_1, s_2, ..., s_N.
她将从序列中选择一些(可能是全部)字符串,然后连接这些保留相对顺序的字符串,以生成一个长字符串。
在所有长度的字符串中 她可以用这种方式产生 K ,找到字典顺序最小的一个。
约束
- 1 ≦ N ≦ 2000
- 1 ≦ K ≦ 10^4
- 对于每个 i, 1 ≦ |s_i| ≦ K.
- |s_1| + |s_2| + ... + |s_N| ≦ 10^6
- 对于每个 i, s_i 由小写字母组成。
- 至少存在一个长度为 伊吕波可以生产的 K 。
输入
输入由标准输入按以下格式给出:
N K s_1 s_2 : s_N
输出
打印长度按字典顺序最小的字符串 应选择 K 。
示例输入 1
3 7 at coder codar
示例输出 1
atcodar
at 和 codar 。
示例输入 2
3 7 coder codar at
示例输出 2
codarat
codar 和 at 。
示例输入 3
4 13 kyuri namida zzzzzzz aaaaaa
示例输出 3
namidazzzzzzz
namida 和 zzzzzzz 。