← 返回题目列表

AtCoder · arc058_d

F. 伊吕波喜欢弦乐

中文机器翻译题面 查看原题

分数: 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 。