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;

//#define FILE_IO
#define dbg(x) cerr << "(" << (__LINE__) << ")" << " " << #x << " = " << x << '\n';

int N, K;
string a, s[2005];
bitset<10005> spl, dp[2005];
vector<int> z;

void zalgo(string s)
{
    int L = s.size();
    z.clear();
    z.resize(L + 1);
    int rgt = 0, lst = 0;
    for(int i = 1; i < L; i++)
    {
        if(rgt >= i)    z[i] = min(rgt - i + 1, z[i - lst]);
        z[i]++;
        while(i + z[i] - 1 < L && s[ z[i] - 1 ] == s[i + z[i] - 1])
            z[i]++;
        z[i]--;
        if(i + z[i] - 1 > rgt)
        {
            rgt = i + z[i] - 1;
            lst = i;
        }
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    scanf("%d%d\n", &N, &K);
    for(int i = 1; i <= N; i++)
        cin >> s[i];

    dp[N + 1][0] = 1;
    for(int i = N; i >= 1; i--)
    {
        dp[i] = dp[i + 1];
        int l = s[i].size();
        dp[i] |= (dp[i + 1] << l);
    }

    spl[0] = 1;
    a = "";
    for(int i = 1; i <= N; i++)
    {
        int l = s[i].size();
        zalgo(s[i] + a);

        int pos = a.size() + 1, st = -1;
        char newch = 0;

        for(int j = 0; j <= a.size() && j + l <= K; j++)
            if(spl[j] && dp[i + 1][K - j - l])
            {
                int cmn = z[j + l];
                if(cmn >= l || j + cmn >= a.size())    continue;

                if(a[j + cmn] > s[i][cmn])
                {
                    if(pos > j + cmn)
                    {
                        pos = j + cmn;
                        st = j;
                        newch = s[i][cmn];
                    }
                    else if(pos == j + cmn && s[i][cmn] < newch)
                    {
                        st = j;
                        newch = s[i][cmn];
                    }
                    else if(pos == j + cmn && s[i][cmn] == newch)
                    {
                        int zz = z[j - st];
                        if(j - st + zz >= l || s[i][zz] < s[i][j - st + zz])
                            st = j;
                    }
                }
            }

        if(pos < a.size())
        {
            int newsz = st;
            for(int i = pos + 1; i <= a.size(); i++)   spl[i] = 0;
            a.resize(newsz);
            a += s[i];
            spl[newsz + l] = 1;
        }
        else
        {
            for(int j = 0; j <= a.size() && j + l <= K; j++)
                if(spl[j] && dp[i + 1][K - j - l])
                {
                    int cmn = z[j + l];
                    if(j + cmn >= a.size())
                    {
                        if(st == -1)
                            st = j;
                        else
                        {
                            int zz = z[j - st];
                            if(j - st + zz >= l || s[i][zz] < s[i][j - st + zz])
                                st = j;
                        }
                    }
                }
            if(st != -1)
            {
                int newsz = st;
                a.resize(newsz);
                a += s[i];
                spl[newsz + l] = 1;
            }
        }

        zalgo(s[i] + a);
        for(int j = 0; j < a.size(); j++)
            if(spl[j] && z[j + l] >= l && dp[i + 1][K - j - l])
                spl[j + l] = 1;
    }

    printf("%s\n", a.c_str());
    return 0;
}