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;

// z[i] = len of lcp of s, s[i..]; lcp(longest common prefix)
vector<int> z_fn(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r)
            z[i] = min(r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]]) {
            z[i]++;
        }
        if (i+z[i]-1 > r) {
            l = i; r = i+z[i]-1;
        }
    }
    return z;
}

const char L = 'a'-1;
const char H = 'z'+1; 
const int N = 2001; 
const int LEN = 10001; 
bool dp[N][LEN];

void solve() {
    int n, T;
    cin >> n >> T;
    vector<string> s(n);
    for (auto& x: s) {
        cin >> x;
    }

    // prep dp
    dp[n][0] = true;
    for (int i = n-1; i >= 0; i--) {
        int len = s[i].size();
        memcpy(dp[i], dp[i+1], sizeof dp[i]);
        for (int j = 0; j <= T; j++) {
            if (j - len >= 0)
                dp[i][j] |= dp[i+1][j-len];
        }
    }

    // sustitute
    vector<bool> cat(T+1, false);
    cat[0] = true;
    string mi(T, H);
    for (int i = 0; i < n; i++) {
        string tmp = s[i] + L + mi;
        auto z = z_fn(tmp);
        int len = s[i].size();
        int id = -1;
        int min_len = T<<1;
        for (int j = T-len; j >= 0; j--) {
            if (!cat[j] || !dp[i+1][T - (j+len)]) continue;
            int lcp = z[len+1+j];
            if (j + lcp >= T) continue;
            if (lcp == len) {
                cat[j+lcp] = true;
            }
            if (lcp >= len) continue;
            if (s[i][lcp] >= mi[j+lcp]) continue;
            if (j+lcp < min_len) {
                id = j;
                min_len = j+lcp;
            }
        }
        if (id == -1) continue;
        for (int j = 0; j < len; j++) {
            mi[id+j] = s[i][j];
        }
        for (int j = id+len; j < T; j++) {
            mi[j] = H;
        }
        for (int j = id+z[len+1+id]+1; j < T; j++) {
            cat[j] = false;
        }
        cat[id+len] = true;
    }
    
    cout << mi;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}