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>
#include <string>

using namespace std;
/*******************************************
****************** BY **********************
******* FUTURE GOOGLE EMPLOYEE *************
****** KARTHICK KUPPURAJ M *****************
********************************************/
#define ms(s, n) memset(s, n, sizeof(s))
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define prec(n) fixed<<setprecision(n)
#define sll(x) scanf("%lld",&x);
#define pll(x) printf("%lld",x);
#define pn printf("\n");
#define ps printf(" ");
#define pc(c) printf("%c",c);
typedef long long int ll;
#define EPS 1e-9
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
bitset<1000002> state, finder[64];
int N, K;
string S[2020];
string Sc;
int idx[2020];
char in[1010101];
bool dp[2020][10101];

char smallest() {
    int pos = 1;
    while (pos < 32)
    {
        if ((state & finder[pos * 2]).none()) pos = pos * 2 + 1;
        else pos *= 2;
    }
    return (pos - 32) + 'a';
}

int main() {
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; ++i)
    {
        scanf("%s", in);
        S[i] = in;
    }

    dp[N][0] = true;
    for (int i = N - 1; i >= 0; --i)
    {
        for (int j = 0; j <= K; ++j)
        {
            if (dp[i + 1][j])
            {
                dp[i][j] = true;
                if (j + S[i].size() <= K) dp[i][j + S[i].size()] = true;
            }
        }
    }
    for (int i = 0; i < N; ++i)
    {
        idx[i] = Sc.size();
        for (char c : S[i])
        { Sc.push_back(c); }
    }
    idx[N] = Sc.size();

    for (int i = 0; i < 64; ++i)
    { finder[i].reset(); }
    for (int i = 0; i < Sc.size(); ++i)
    {
        finder[Sc[i] - 'a' + 32].set(i);
    }
    for (int i = 31; i >= 1; --i)
    { finder[i] = finder[i * 2] | finder[i * 2 + 1]; }

    state.reset();
    state.set(0, true);

    string ret;

    for (int i = 0; i < K; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (state[idx[j]]) state.set(idx[j + 1]);
        }
        for (int j = 0; j < N; ++j)
        {
            if (K - i - (int) S[j].size() < 0 || !dp[j + 1][K - i - S[j].size()]) state.reset(idx[j]);
        }

        char nxt = smallest();
        ret.push_back(nxt);
        state &= finder[(nxt - 'a') + 32];
        state <<= 1;
    }

    puts(ret.c_str());

    return 0;
}