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 <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_set>
# include <unordered_map>
using namespace std;


int n, m;
string s[2005];
bool dp[2005][10005], st[10005];
string s1;
int len[2005];

int main(int argc, const char * argv[]) {
#ifdef __APPLE__
    freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        len[i] = (int)s[i].size();
    }
    dp[n][m] = true;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = dp[i + 1][j];
            if (j + len[i + 1] <= m && dp[i + 1][j + len[i + 1]]) dp[i][j] = true;
        }
    }
    st[0] = true;
    s1 = "";
    for (int i = 1; i <= n; ++i) {
        string s2 = s[i] + "#" + s1;
        int nn = (int)s2.size();
        vector<int> z(nn, 0);
        for (int j = 1, l = 0, r = 0; j < nn; ++j) {
            if (j <= r) z[j] = min(r - j + 1, z[j - l]);
            while (j + z[j] < nn && s2[z[j]] == s2[j + z[j]]) ++z[j];
            if (j + z[j] - 1 > r) l = j, r = j + z[j] - 1;
        }
        for (int j = len[i]; j <= m; ++j) if (dp[i][j]) {
            int l1 = j - len[i];
            if (!st[l1]) continue;
            int l = len[i] + l1 + 1;
            bool c = false;
            if (l >= nn) c = true;
            else {
                int r = l + z[l];
                if (z[l] < len[i] && (r >= nn || s2[r] > s2[z[l]])) {
                    c = true;
                }
            }
            if (c) {
                string s2 = "";
                for (int k = 1; k <= l1; ++k)
                    s2 += s1[k - 1];
                s2 += s[i];
                s1 = s2;
                for (int k = l1 + 1 + (l >= nn ? 10005: z[l]); k <= m; ++k)
                    st[k] = false;
                st[j] = true;
                break;
            }
        }
        for (int j = 0; j <= m; ++j)
            if (!dp[i][j]) st[j] = false;
        int pos = 0;
        s2 = "";
        for (int j = 0; j <= m; ++j)
            if (st[j]) pos = j;
        for (int j = 1; j <= pos; ++j)
            s2 += s1[j - 1];
        s1 = s2;
    }
    cout << s1 << '\n';
    return 0;
}