题目描述

いろは酱有 $N$ 个字符串 $s_1,\ s_2,\ ...,\ s_N$。

いろは酱会从中选择若干字符串，并按照下标递增的顺序将选中的字符串连接起来，构成一个长度为 $K$ 的字符串。

请你求出所有可以构成的长度为 $K$ 的字符串中，字典序最小的那个。

输入格式

输入以如下格式从标准输入读入。

$N$ $K$ $s_1$ $s_2$ : $s_N$

输出格式

请输出所有可以构成的长度为 $K$ 的字符串中，字典序最小的那个。

样例 1

输入

3 7
at
coder
codar

输出

atcodar

样例 2

输入

3 7
coder
codar
at

输出

codarat

样例 3

输入

4 13
kyuri
namida
zzzzzzz
aaaaaa

输出

namidazzzzzzz

说明/提示

限制条件

• $1\leq N\leq 2000$
• $1\leq K\leq 10^4$
• $1\leq |s_i|\leq K$
• $|s_1|+|s_2|+\cdots+|s_N|\leq 10^6$
• 对于每个 $i$，$s_i$ 均为仅由小写英文字母组成的字符串。
• 保证一定存在构造长度为 $K$ 的字符串的方法。

样例解释 1

选择 at 和 codar。

样例解释 2

选择 codar 和 at。

样例解释 3

选择 namida 和 zzzzzzz。

由 ChatGPT 4.1 翻译