配点 : $1500$ 点

問題文

いろはちゃんは $N$ 個の文字列 $s_1, s_2, ..., s_N$ を持っています。

いろはちゃんは、この中からいくつか文字列を選びます。そして添字の昇順で選んだ文字列を繋げ、長さ $K$ の文字列を作ります。

作れる長さ $K$ の文字列のうち、もっとも辞書順で小さいものを求めてください。

制約

• $1 \leq N \leq 2000$
• $1 \leq K \leq 10^4$
• $1 \leq |s_i| \leq K$
• $|s_1| + |s_2| + ... + |s_N| \leq 10^6$
• 各 $i$ について, $s_i$ は全て半角英小文字のみから成る文字列である。
• 長さ $K$ の文字列を作る方法が存在することが保証される。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$s_1$

$s_2$

:

$s_N$

出力

作れる長さ $K$ の文字列のうち、もっとも辞書順で小さいものを出力せよ。

3 7
at
coder
codar

atcodar

at と codar を選択します。

3 7
coder
codar
at

codarat

codar と at を選択します。

4 13
kyuri
namida
zzzzzzz
aaaaaa

namidazzzzzzz

namida と zzzzzzz を選択します。