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;
//using namespace atcoder;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define pb push_back
#define fi first
#define se second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void chOut(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using v_bool = vector<bool>;
using v_Pii = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;

vector<int> z_algorithm(string A){
    int N = A.size();
    vector<int> Z(N);
    Z[0] = N;
    int i = 1, j = 0;
    while(i < N){
        while(i + j < N && A[j] == A[i + j]) j++;
        Z[i] = j;
        if(j == 0) { i++; continue; }
        int k = 1;
        while(i + k < N && k + Z[k] < j){
            Z[i + k] = Z[k];
            k++;
        }
        i += k; j -= k;
    }
    return Z;
}

using bset = bitset<10001>;
//using bset = bitset<14>;

signed main(){

    int N, K; cin >> N >> K;
    vector<string> s(N); cin >> s;

    vector<bset> dp(N + 1);
    dp[N][K] = 1;
    IREP(i, N) dp[i] = dp[i + 1] | (dp[i + 1] >> SZ(s[i]));
    
    string T = "";
    v_bool ok(K + 1, false);
    ok[0] = true;
    REP(i, N){
        vec z = z_algorithm(s[i] + '@' + T);
        v_Pii p;
        int n = SZ(s[i]), m = SZ(T);

        REP(k, K + 1) if(dp[i + 1][k]){
            if(ok[k]){
                while(true){
                    bool next = false;
                    if(SZ(p) == 0) p.pb(Pii(k, 0));
                    else{
                        if(p.back().se == 0) p.pb(Pii(k, 0));
                        else{
                            int u = p.back().fi - n;
                            int c = z[n + 1 + u];
                            if(c == n) p.pb(Pii(k, 0));
                            else if(T[u + c] < s[i][c]){
                                p.pop_back();
                                next = true;
                            }
                        }
                    }
                    if(!next) break;
                }
            }
            if(k - n >= 0 && ok[k - n]){
                while(true){
                    bool next = false;
                    if(SZ(p) == 0) p.pb(Pii(k, 1));
                    else{
                        if(p.back().se == 0){
                            int u = k - n;
                            int c = z[n + 1 + u];
                            if(u + c >= p.back().fi) p.pb(Pii(k, 1));
                            else if(s[i][c] < T[u + c]){
                                p.pop_back();
                                next = true;
                            }
                        }else{
                            int u = p.back().fi - n;
                            int c = z[n + 1 + u];
                            if(c >= k - n - u){
                                c = z[k - n - u];
                                if(c + (k - n - u) == n) p.pb(Pii(k, 1));
                                else if(s[i][c] < s[i][c + (k - n - u)]){
                                    p.pop_back();
                                    next = true;
                                }
                            }else{
                                if(c == n) p.pb(Pii(k, 1));
                                else if(T[u + c] < s[i][c]) {
                                    p.pop_back();
                                    next = true;
                                }
                            } 
                        }
                    }
                    if(!next) break;
                }
            }
        }
    
        fill(all(ok), false);
        for(Pii q: p) ok[q.fi] = true;
        Pii q = p.back();
        if(q.se == 0) T = T.substr(0, q.fi);
        else T = T.substr(0, q.fi - n) + s[i];
    }
    Out(T);

    return 0;
}