题目描述

Mikaeel 有 $n$ 个字符串 $s_{1}, \ldots, s_{n}$，每个字符串都由小写英文字母组成。他需要从每个字符串中选取一个非空子串，并将这些子串按顺序拼接起来，最终形成一个长度为 $k$ 的字符串。请帮助 Mikaeel 构造出字典序最小的可能字符串。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示字符串的数量和最终字符串的长度。

接下来的 $n$ 行依次给出 Mikaeel 的字符串序列 $s_{1}, \ldots, s_{n}$。

输出格式

在一行中输出可以构造出的字典序最小的字符串。

3 5
abc
xxx
aaa

abcxa

5 6
ab
bz
zb
aa
cb

abbaab

提示

数据范围

• $n, \sum_{i=1}^{n}\left|s_{i}\right| \leq 4000$
• $n \leq k \leq \sum_{i=1}^{n}\left|s_{i}\right|$

子任务

翻译由 DeepSeek V3 完成