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:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
const int maxK = 1e4 + 5;
typedef bitset < maxK > bs;
const ull one = 1;
int n, k;
const int maxN = 2005;
string s[maxN];
bs can[maxN];
struct myBitset{
    vector < ull > f;
    myBitset(int x) : f(x / 64 + 1) {}

    myBitset() {

    }

    void shift() {
        for (int i = f.size() - 1; i >= 0; i--) {
            if (i + 1 < f.size() && (f[i] & (one << 63))) {
                f[i + 1] |= 1;
            }
            f[i] = f[i] << 1;
        }
    }
    bool get(int x) {
        return (bool)((f[x / 64] >> (x & 63)) & one);
    }

    void set(int x, bool p) {
        if (p) {
            f[x / 64] |= (one << (x & 63));
        }
        else {
            f[x / 64] |= (one << (x & 63));
            f[x / 64] ^= (one << (x & 63));
        }
    }

    bool can_and(myBitset& other) {
        bool c = false;
        for (int i = 0; i < f.size(); i++) {
            c |= (f[i] & other.f[i]);
        }
        return c;
    }

    void do_and(myBitset& other) {
        for (int i = 0; i < f.size(); i++) {
            f[i] &= other.f[i];
        }
    }
};

myBitset bits[maxN];
myBitset at_most[maxN][27];
myBitset at_least[maxN][27];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    can[n + 1][0] = true;
    for (int i = n; i >= 1; i--) {
        can[i] = (can[i + 1] | (can[i + 1] << s[i].size()));
    }
    int best = 26;
    for (int i = 1; i <= n; i++) {
        if (can[i + 1][k - s[i].size()]) {
            best = min(best, (int)(s[i][0] - 'a'));
        }
    }
    assert(best != 26);
    string ans;
    ans += (char)(best + 'a');
    for (int i = 1; i <= n; i++) {
        bits[i] = myBitset(s[i].size());
        if (can[i + 1][k - s[i].size()] && s[i][0] == best + 'a') {
            bits[i].set(0, true);
        }
        for (int j = 0; j < 26; j++) {
            at_most[i][j] = myBitset(s[i].size());
            at_least[i][j] = myBitset(s[i].size());
            for (int p = 0; p < s[i].size(); p++) {
                if (s[i][p] - 'a' <= j) {
                    at_most[i][j].set(p, true);
                }
                if ((int)(s[i][p] - 'a') > j) {
                    at_least[i][j].set(p, false);
                }
                else {
                    at_least[i][j].set(p, true);
                }
            }
        }
    }
    for (int len = 2; len <= k; len++) {
        int at_least = n + 1;
//        cout << 1 << " " << bits[1].f[0] << " HI " << endl;
        for (int i = 1; i <= n; i++) {
            if (bits[i].get(s[i].size() - 1)) {
                at_least = i;
                break;
            }
        }
//        cout << len << " " << at_least << endl;
        for (int i = n; i >= 1; i--) {
            bits[i].shift();
            bits[i].set(s[i].size(), 0);
            if (i >= at_least + 1 && k - len + 1 >= s[i].size() && can[i + 1][k - len + 1 - s[i].size()]) bits[i].set(0, true);
        }
        int l = -1;
        int r = 25;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            bool ok = false;
            for (int j = 1; j <= n; j++) {
                if (bits[j].can_and(at_most[j][mid])) {
                    ok = true;
                    break;
                }
            }
            if (ok) r = mid;
            else l = mid;
        }
//        cout << "GOT " << r << endl;
        ans += (char)(r + 'a');
        for (int i = n; i >= 1; i--) {
            bits[i].do_and(::at_least[i][r]);
        }
    }
    cout << ans;
    return 0;
}