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:
//const int K = 10001;
//vi suffix_badness(string s){
//    SuffixArray sa(s);
//    vi ans(sz(s));
//    int badness = 0;
//    rep(i,0,sz(s)-1){
//        ans[sa.sa[i]] = badness;
//        if(sa.lcp[i] != sz(s)-sa.sa[i])
//            ++badness;
//    }
//    return ans;
//}
//string solve(int n, int k, vs arr){
//    vector<bitset<K>> can_finish(n+1);
//    can_finish[n][k] = true;
//    for(int i = n; i >= 1; --i)
//        can_finish[i-1] = can_finish[i] | (can_finish[i] >> sz(arr[i-1]));
//    string s = "";
//    vb splits(K);
//    splits[0] = true;
//    rep(i,0,n-1){
//        vi badness = suffix_badness(arr[i]);
//        vi match_len = z_alg(arr[i]+s);
//        match_len = vi(match_len.begin()+sz(arr[i]),match_len.end());
//        match_len.pb(sz(arr[i]));
//        vvi upgrades;
//        for(int keep = sz(s); keep >= 0; --keep){
//            if(keep+sz(arr[i]) > k) continue;
//            if(!splits[keep]) continue;
//            if(!can_finish[i+1][keep+sz(arr[i])]) continue;
//            int same = min(match_len[keep],int(sz(arr[i])));
//            same = min(same,int(sz(s))-keep);
//            if(same == sz(arr[i])){
//                splits[keep+same] = true;
//                continue;
//            }
//            if(same+keep == sz(s)){
//                upgrades.pb({same+keep,badness[same],same});
//            }else{
//                int nxt_diff = same+keep;
//                if(arr[i][same] > s[nxt_diff]) continue;
//                upgrades.pb({same+keep,badness[same],same});
//            }
//        }
//        if(upgrades.empty()) continue;
//        //assert(!upgrades.empty());
//        sort(all(upgrades));
//        while(
//                upgrades.back()[0] != upgrades[0][0] ||
//                upgrades.back()[1] != upgrades[0][1])
//            upgrades.pop_back();
//        int same_keep = upgrades[0][0];
//        int same = upgrades[0][2];
//        s = s.substr(0,same_keep) + arr[i].substr(same);
//        splits[sz(s)] = true;
//        fill(splits.begin()+same_keep+1,splits.end(),false);
//        for(auto _ : upgrades){
//            int total_len = _[0] + sz(arr[i]) - _[2];
//            assert(total_len <= sz(s));
//            splits[total_len] = true;
//        }
//    }
//    return s;
//}
//string bf(int n, int k, vs arr){
//    assert(n == sz(arr));
//    vs dp(k+1);
//    for(string s : arr){
//        for(int i = k-sz(s); i >= 0; --i){
//            if(sz(dp[i]) == i){
//                string nxt = dp[i]+s;
//                if(dp[i+sz(s)].empty())
//                    dp[i+sz(s)] = nxt;
//                dp[i+sz(s)] = min(dp[i+sz(s)],nxt);
//            }
//        }
//    }
//    return dp[k];
//}
//void input(){
//    int n,k;
//    cin >> n >> k;
//    vs arr(n);
//    cin >> arr;
//    print(solve(n,k,arr));
//    exit(0);
//}
//void _(){
//    input();
//    int iter = 0;
//    while(true){
//        ++iter;
//        watch(iter);
//        int mx = 1000;
//        int my = 10;
//        int n = rand()%mx+1;
//        int k = rand()%mx+1;
//        vs arr;
//        rep(i,1,n){
//            int sz = rand()%mx+1;
//            string s;
//            rep(j,1,sz)
//                s.pb(rand()%my+'a');
//            arr.pb(s);
//        }
//        if(bf(n,k,arr) != solve(n,k,arr)){
//            cout << n << ' ' << k << '\n';
//            print(arr,"\n");
//            exit(0);
//        }
//    }
//}
//
#include <cstring>
#include <bitset>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_INT(i,l,r) for(int i = l; i <= r; ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define watch(x) cerr << (#x) << " = " << x << '\n'
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
T1 istream& read(T, T, istream& = cin);
T1 istream& operator>>(istream& stream, vector<T>& t){
    return read(all(t), stream);
}
T1 istream& read(T b, T e, istream& stream){
    for(T it = b; it != e; ++it)
        stream >> *it;
    return stream;
}
T1 void print(T x, string end = "\n"){
    cout << x << end;
}
T1 vector<int> z_alg(vector<T>& s){
    vector<int> z(sz(s));
    int n = sz(s);
    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[0] = sz(s);
    return z;
}
static vector<int> z_alg(string s){
    vector<char> t(all(s));
    return z_alg(t);
}
class SuffixArray{
    void make_lcp(int const*s){
        for(int i=0, k=0;i<n;++i)
            if(inv[i]!=0){
                for(int j = sa[inv[i]-1];k<n-max(i, j) && s[i+k]==s[j+k];++k);
                lcp[inv[i]-1]=k;
                if(k)--k;
            } else k=0;
    }
    bool cmp(vector<int> const&rank,int i,int j,int l){
        return i<n-l && j<n-l && rank[i]==rank[j] && rank[i+l]==rank[j+l];
    }
    void build_SA(int const*s){
        int m = max(256, n);
        sa.resize(n);
        vector<int> x(n), y(n), buck(m);
        int i,j,p;
        for(i=0;i<n;++i) buck[x[i]=s[i]]++;
        for(i=1;i<m;++i) buck[i]+=buck[i-1];
        for(i=n-1;i>=0;--i) sa[--buck[x[i]]]=i;
        for(p=0,j=1;p+1<n;m=p+1,j*=2) {
            for(p=0,i=n-j;i<n;++i) y[p++]=i;
            for(i=0;i<n;++i) if (sa[i]>=j) y[p++]=sa[i]-j;
            memset(buck.data(),0,sizeof(int)*(m));
            for(i=0;i<n;++i) ++buck[x[y[i]]];
            for(i=1;i<m;++i) buck[i]+=buck[i-1];
            for(i=n-1;i>=0;--i) sa[--buck[x[y[i]]]]=y[i];
            x.swap(y);
            for(p=0,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j) ? p : ++p;
        }
        x.swap(inv); y.swap(lcp);
        for(int i=0;i<n;++i) inv[sa[i]]=i;
        make_lcp(s);
    }
    public:
    SuffixArray(int const*s, int _N):n(_N){build_SA(s);}
    SuffixArray(vector<int> const&s):SuffixArray(s.data(), s.size()){}
    SuffixArray(char const*s, int _N):n(_N){build_SA(vector<int> (s, s+n).data());}
    SuffixArray(string const&s):SuffixArray(s.data(), s.size()){}
    vector<int> sa, inv, lcp;
    const int n;
};
T1 ostream& print(T b, T e, string sep = " ", ostream& stream = cout){
    for(T it = b; it != e; ++it){
        stream << *it;
        if(it + 1 != e)
            stream << sep;
    }
    return stream;
}
T1 void print(vector<T> arr, string sep = " "){
    if(arr.empty()){
        return;
    }
    print(arr.begin(), arr.end(), sep);
    cout << '\n';
}
const int K = 10001;
vi suffix_badness(string s){
    SuffixArray sa(s);
    vi ans(sz(s));
    int badness = 0;
    rep(i,0,sz(s)-1){
        ans[sa.sa[i]] = badness;
        if(sa.lcp[i] != sz(s)-sa.sa[i])
            ++badness;
    }
    return ans;
}
string solve(int n, int k, vs arr){
    vector<bitset<K>> can_finish(n+1);
    can_finish[n][k] = true;
    for(int i = n; i >= 1; --i)
        can_finish[i-1] = can_finish[i] | (can_finish[i] >> sz(arr[i-1]));
    string s = "";
    vb splits(K);
    splits[0] = true;
    rep(i,0,n-1){
        vi badness = suffix_badness(arr[i]);
        vi match_len = z_alg(arr[i]+s);
        match_len = vi(match_len.begin()+sz(arr[i]),match_len.end());
        match_len.pb(sz(arr[i]));
        vvi upgrades;
        for(int keep = sz(s); keep >= 0; --keep){
            if(keep+sz(arr[i]) > k) continue;
            if(!splits[keep]) continue;
            if(!can_finish[i+1][keep+sz(arr[i])]) continue;
            int same = min(match_len[keep],int(sz(arr[i])));
            same = min(same,int(sz(s))-keep);
            if(same == sz(arr[i])){
                splits[keep+same] = true;
                continue;
            }
            if(same+keep == sz(s)){
                upgrades.pb({same+keep,badness[same],same});
            }else{
                int nxt_diff = same+keep;
                if(arr[i][same] > s[nxt_diff]) continue;
                upgrades.pb({same+keep,badness[same],same});
            }
        }
        if(upgrades.empty()) continue;
        //assert(!upgrades.empty());
        sort(all(upgrades));
        while(
                upgrades.back()[0] != upgrades[0][0] ||
                upgrades.back()[1] != upgrades[0][1])
            upgrades.pop_back();
        int same_keep = upgrades[0][0];
        int same = upgrades[0][2];
        s = s.substr(0,same_keep) + arr[i].substr(same);
        splits[sz(s)] = true;
        fill(splits.begin()+same_keep+1,splits.end(),false);
        for(auto _ : upgrades){
            int total_len = _[0] + sz(arr[i]) - _[2];
            assert(total_len <= sz(s));
            splits[total_len] = true;
        }
    }
    return s;
}
string bf(int n, int k, vs arr){
    assert(n == sz(arr));
    vs dp(k+1);
    for(string s : arr){
        for(int i = k-sz(s); i >= 0; --i){
            if(sz(dp[i]) == i){
                string nxt = dp[i]+s;
                if(dp[i+sz(s)].empty())
                    dp[i+sz(s)] = nxt;
                dp[i+sz(s)] = min(dp[i+sz(s)],nxt);
            }
        }
    }
    return dp[k];
}
void input(){
    int n,k;
    cin >> n >> k;
    vs arr(n);
    cin >> arr;
    print(solve(n,k,arr));
    exit(0);
}
void _(){
    input();
    int iter = 0;
    while(true){
        ++iter;
        watch(iter);
        int mx = 1000;
        int my = 10;
        int n = rand()%mx+1;
        int k = rand()%mx+1;
        vs arr;
        rep(i,1,n){
            int sz = rand()%mx+1;
            string s;
            rep(j,1,sz)
                s.pb(rand()%my+'a');
            arr.pb(s);
        }
        if(bf(n,k,arr) != solve(n,k,arr)){
            cout << n << ' ' << k << '\n';
            print(arr,"\n");
            exit(0);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        _();
}