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;

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

typedef bitset<10001>bs;

int N,K;
string S[2222];

bs able[2222];

vint zalgorithm(string s){
    vint a(s.size());
    a[0]=s.size();
    int i=1,j=0;
    while(i<s.size()){
        while(i+j<s.size()&&s[j]==s[i+j])j++;
        a[i]=j;
        if(j==0){i++;continue;}
        int k=1;
        while(i+k<s.size()&&k+a[k]<j)a[i+k]=a[k],k++;
        i+=k;j-=k;
    }
    return a;
}

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

    cin>>N>>K;
    rep(i,N)cin>>S[i];

    able[N][0]=1;
    for(int i=N-1;i>=0;i--)able[i]=able[i+1]|(able[i+1]<<S[i].size());

    string s;
    bs ok;
    ok[0]=1;

    for(int i=0;i<N;i++){
        string ss=S[i]+s;
        vint a=zalgorithm(ss);
        bs okok=ok;

        vint latte;

        for(int j=0;j<=s.size();j++){
            if(j+S[i].size()>K)continue;
            if(!ok[j])continue;
            if(!able[i+1][K-j-(int)S[i].size()])continue;

            int lcp;
            if(j==s.size())lcp=0;
            else lcp=a[S[i].size()+j];
            chmin(lcp,S[i].size());
            if(lcp==s.size()-j){
                s+=S[i].substr(lcp,S[i].size()-lcp);
                okok[s.size()]=1;
            }
            else if(lcp==S[i].size()){
                okok[j+S[i].size()]=1;
            }
            else if(s[j+lcp]>S[i][lcp]){
                bool f=true;
                while(latte.size()){
                    int k=latte.back();
                    int tmp=a[S[i].size()+k];
                    if(tmp<j-k){
                        f=false;
                        break;
                    }
                    tmp=a[j-k];
                    if(tmp<S[i].size()-(j-k))latte.pop_back();
                    else break;
                }
                if(f)latte.pb(j);
            }
        }

        if(latte.size()){
            int k=latte.back();
            s=s.substr(0,k)+S[i];
            int tmp=a[S[i].size()+k];
            for(int j=k+tmp+1;j<=K;j++)okok[j]=0;
            for(auto w:latte)okok[w+S[i].size()]=1;
        }

        ok=okok;
    }

    cout<<s<<endl;
    return 0;
}