Problem: 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.

Examples

Input

3 7
at
coder
codar


Output

atcodar


Input

3 7
coder
codar
at


Output

codarat


Input

4 13
kyuri
namida
zzzzzzz
aaaaaa


Output

namidazzzzzzz

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
const int maxn = 2007, maxk = int(2e4) + 7, inf = 0x3f3f3f3f;
char str[maxn][maxk], ans[maxk];
bool f[maxn][maxk];
int len_str[maxn], len_set, n, k;
struct { int index, pos; } set[3][maxn << 1];
bool judge() {
    int ch_cnt[128] = {0}, tot_cnt = 0;
    char ch_cur = 'a';
    for (int i = 1; i <= n; i++) for (int j = 1; j <= len_str[i]; j++) ch_cnt[str[i][j]]++;
    for (char ch = 'a'; ch <= 'z'; ch++) if (ch_cnt[ch]) tot_cnt++, ch_cur = ch;
    if (tot_cnt == 1) {
        for (int i = 1; i <= k; i++) printf("%c%s", ch_cur, i == k ? "\n" : "");
        return true;
    }
    return false;
}
int main() {
//    freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%s", str[i] + 1);
        len_str[i] = int(strlen(str[i] + 1));
    }
    if (judge()) return 0;
    f[n + 1][0] = true;
    for (int i = n, suf_sum = 0, upper; i >= 1; i--) {
        suf_sum += len_str[i], upper = std::min(suf_sum, k);
        for (int j = 0; j <= upper; j++) {
            f[i][j] = f[i + 1][j];
            if (j >= len_str[i]) f[i][j] |= f[i + 1][j - len_str[i]];
        }
    }
    for (int i = 1; i <= n; i++) if (f[i + 1][k - len_str[i]]) set[0][++len_set] = {i, 1};
    for (int i = 1, cur = 0, new_len_set, min_index; i <= k; i++) {
        char min_ch = 127;
        for (int j = 1, index, pos; j <= len_set; j++) {
            index = set[cur][j].index, pos = set[cur][j].pos;
            if (min_ch > str[index][pos]) min_ch = str[index][pos];
        }
        ans[i] = min_ch, new_len_set = 0, min_index = inf;
        for (int j = 1, index, pos; j <= len_set; j++) {
            index = set[cur][j].index, pos = set[cur][j].pos;
            if (str[index][pos] > min_ch) continue;
            if (pos < len_str[index]) set[cur ^ 1][++new_len_set] = {index, pos + 1};
            else if (index < min_index) min_index = index;
        }
        for (int j = min_index + 1; j <= n; j++) if (len_str[j] <= k - i && f[j + 1][k - i - len_str[j]])
                set[cur ^ 1][++new_len_set] = {j, 1};
        len_set = new_len_set, cur ^= 1;
    }
    for (int i = 1; i <= k; i++) printf("%c%s", ans[i], i == k ? "\n" : "");
    return 0;
}