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>
using namespace std;

int n, k;
string s[2005], ans;
bitset <10001> ok[2005];
bitset <10001> dp[2005];

int z[10005];
void do_z(string s){
    memset(z, 0, sizeof(z));

    int L = s.size();
    for(int i = 1, last = 0, right = 0; i < L ; ++i){
        if(i <= right) z[i] = min(right - i + 1, z[i - last]);

        while(i + z[i] < L && s[z[i]] == s[i + z[i]]) ++z[i];
        if(i + z[i] - 1 > right) right = i + z[i] - 1, last = i;
    }
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n >> k;
    for(int i = 1; i <= n ; ++i) cin >> s[i];

    ok[n + 1][0] = true;
    for(int i = n; i >= 1 ; --i){
        ok[i] = ok[i + 1];
        ok[i] = ok[i] | (ok[i + 1] << (s[i].size()));
    }

    dp[0][0] = 1;
    for(int i = 1; i <= n ; ++i){
        do_z(s[i] + ans);

        dp[i] = dp[i - 1];
        int L = s[i].size();
        for(int j = L; j - L <= ans.size() && j <= k ; ++j){
            if(dp[i - 1][j - L] == false || ok[i + 1][k - j] == false) continue ;

            int aux = z[j];
            if(aux >= L){
                dp[i][j] = true;
                continue ;
            }

            if(j - L == ans.size() || s[i][aux] < ans[j - L + aux]){
                ans = ans.substr(0, j - L) + s[i];
                for(int t = j - L + aux + 1 ; t <= k ; ++t) dp[i][t] = false;
                dp[i][j] = true;
                break ;
            }

        }
    }

    cout << ans;

    return 0;
}