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 <string>
#include <algorithm>
#include <bitset>
#include <vector>

using namespace std;

#define MAXN 2000
#define MAXK 10000

bitset <MAXK+1> d[MAXN+1];
int r[MAXK+1];
string s[MAXN+1];

vector <int> u[MAXN+1];

char ans[MAXK+1];
int a[MAXN+1], b[MAXN+1];
int st[MAXN+1];

bool g[MAXN+1][MAXN+1];

bool cmp(const int &a, const int &b){
    return s[a]<s[b];
}

int main(){
    int n, k;
    cin >> n >> k;

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

    for(int i=1; i<=n; i++)
        a[i]=i;

    sort(a+1, a+n+1, cmp);

    int q=1;
    b[a[1]]=1;
    for(int i=2; i<=n; i++){
        q+=(s[a[i]]!=s[a[i-1]]);
        b[a[i]]=q;
    }

    int vf=1;
    st[1]=a[1];
    for(int i=2; i<=n; i++){
        int j=0, p=1;
        while((p<=vf)&&(j<(int)s[a[i]].size())&&(s[a[i]][j]==s[st[p]][j])){
            j++;
            while((p<=vf)&&(j==(int)s[st[p]].size()))
                p++;
        }
        st[p]=a[i];
        vf=p;
        for(int j=1; j<p; j++)
            g[a[i]][st[j]]=g[st[j]][a[i]]=1;
    }

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

    r[0]=1;
    int t=0;
    for(int i=0; i<k; i++) if(r[i]>0){
        int left=q+1, right=0;
        for(int j=r[i]; j<=n; j++)
            if((k-i-(int)s[j].size()>=0)&&(d[j+1][k-i-(int)s[j].size()]))
                u[b[j]].push_back(j), left=min(left, b[j]), right=max(right, b[j]);

        r[i]=0;

        vf=0;
        for(int j=left; j<=right; j++){
            for(auto x:u[j])
                if((vf==0)||(g[st[vf]][x]))
                    st[++vf]=x;
            u[j].clear();
        }

        int p=0, j=1;
        while((i+p<t)&&(j<=vf)&&(ans[i+p]==s[st[vf]][p])){
            p++;
            while((j<=vf)&&((int)s[st[j]].size()==p)){
                if((r[i+p]==0)||(st[j]+1<r[i+p]))
                    r[i+p]=st[j]+1;
                j++;
            }
        }

        if((j<=vf)&&((i+p==t)||(s[st[vf]][p]<ans[i+p]))){
            while(j<=vf){
                ans[i+p]=s[st[vf]][p];
                p++;
                r[i+p]=0;
                while((j<=vf)&&((int)s[st[j]].size()==p)){
                    if((r[i+p]==0)||(st[j]+1<r[i+p]))
                        r[i+p]=st[j]+1;
                    j++;
                }
            }
            while(i+p<t){
                p++;
                r[i+p]=0;
            }

            t=i+p;
        }
    }

    for(int i=0; i<k; i++)
        cout << ans[i];

    return 0;
}