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;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back
string s[2005], dp[2005];
bool vis[10005], vis2[10005];
bool ok[2005][10005];
struct z_function{
    string s;
    int z[20005];
    int n;
    void init(string s1, string s2, int l1, int l2){
        s.clear();
        for(int i=0;i<l1;i++) s += s1[i];
        s += '#';
        for(int i=0;i<l2;i++) s += s2[i];
        n = l1+1+l2;
    }
    void cal(){
        int L = 0, R = 0;
        for(int i=1;i<n;i++){
            if(i > R){
                L = R = i;
                while(R < n && s[R-L] == s[R]) R++;
                z[i] = R-L;
                R--;
            }
            else{
                int k = i-L;
                if(z[k] < R-i+1){
                    z[i] = z[k];
                }
                else{
                    L = i;
                    while(R < n && s[R-L] == s[R]) R++;
                    z[i] = R-L;
                    R--;
                }
            }
        }
    }
}z;
int z1[20005], z2[20005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> s[i];
    ok[n][k] = 1;
    for(int i=n-1;i>=0;i--){
        int l = s[i].length();
        for(int j=k;j>=0;j--){
            if(ok[i+1][j] && j-l >= 0) ok[i][j-l] = 1;
            if(ok[i+1][j]) ok[i][j] = 1;
        }
    }
    vis[0] = 1;
    for(int i=0;i<n;i++){
        int l1 = s[i].length(), l2 = dp[i].length();
        z.init(s[i], dp[i], l1, l2);
        z.cal();
        for(int j=0;j<l1;j++) z1[j] = z.z[j];
        for(int j=0;j<l2;j++) z2[j] = z.z[l1+1+j];

        int idx = 1e9;
        for(int j=0;j<=l2;j++){
            if(j+l1 <= k && vis[j] && ok[i+1][j+l1]){
                if(idx == 1e9){
                    if(j == l2) idx = j;
                    else{
                        int val = z2[j];
                        if(val < l1){
                            if(j+val < l2){
                                if(s[i][val] < dp[i][j+val]) idx = j;
                            }
                            else idx = j;
                        }
                    }
                }
                else{
                    if(j-idx > l1) break;
                    int val = z2[idx];
                    int x = j-idx;
                    if(val < x){
                        if(dp[i][idx+val] < s[i][val]) idx = j;
                    }
                    else{
                        val = z1[x];
                        if(val >= l1-x) idx = j;
                        else{
                            if(s[i][val] < s[i][x+val]) idx = j;
                        }
                    }
                }
            }
        }

        if(idx != 1e9){
            memset(vis2, 0, sizeof(vis2));
            for(int j=0;j<=l2;j++){
                if(!vis[j]) continue;
                if(j <= idx){
                    vis2[j] = vis[j];
                    if(idx-j >= l1){
                        int val = z2[j];
                        if(val >= l1) vis2[j+l1] = 1;
                    }
                    else{
                        int val = z2[j];
                        int x = idx-j;
                        if(val >= x){
                            val = z1[x];
                            if(val >= l1-x) vis2[j+l1] = 1;
                        }
                    }
                }
                else{
                    int val = z2[idx];
                    if(val >= j-idx) vis2[j] = 1;
                }
            }
            vis2[idx+l1] = 1;
            memset(vis, 0, sizeof(vis));
            for(int j=0;j<=k;j++) vis[j] = vis2[j];
        }

        if(idx == 1e9) dp[i+1] = dp[i];
        else dp[i+1] = dp[i].substr(0, idx) + s[i];
    }
    cout << dp[n] << endl;
}