AtCoder Regular Contest 058

F - 文字列大好きいろはちゃん / Iroha Loves Strings


Time limit時間制限 : 5sec / Memory limitメモリ制限 : 768MB

配点 : 1500

問題文

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

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

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

制約

  • 1 ≦ N ≦ 2000
  • 1 ≦ K ≦ 10^4
  • 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

atcodar を選択します。


入力例 2

3 7
coder
codar
at

出力例 2

codarat

codarat を選択します。


入力例 3

4 13
kyuri
namida
zzzzzzz
aaaaaa

出力例 3

namidazzzzzzz

namidazzzzzzz を選択します。

Score : 1500 points

Problem Statement

Iroha has a sequence of N strings s_1, s_2, ..., s_N.

She will choose some (possibly all) strings from the sequence, then concatenate those strings retaining the relative order, to produce a long string.

Among all strings of length K that she can produce in this way, find the lexicographically smallest one.

Constraints

  • 1 ≦ N ≦ 2000
  • 1 ≦ K ≦ 10^4
  • For each i, 1 ≦ |s_i| ≦ K.
  • |s_1| + |s_2| + ... + |s_N| ≦ 10^6
  • For each i, s_i consists of lowercase letters.
  • There exists at least one string of length K that Iroha can produce.

Input

The input is given from Standard Input in the following format:

N K
s_1
s_2
:
s_N

Output

Print the lexicographically smallest string of length K that Iroha can produce.


Sample Input 1

3 7
at
coder
codar

Sample Output 1

atcodar

at and codar should be chosen.


Sample Input 2

3 7
coder
codar
at

Sample Output 2

codarat

codar and at should be chosen.


Sample Input 3

4 13
kyuri
namida
zzzzzzz
aaaaaa

Sample Output 3

namidazzzzzzz

namida and zzzzzzz should be chosen.


Submit提出する