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;

const int NMAX = 2e3 + 5;
const int KMAX = 1e4 + 5;

int z[KMAX << 1];

string str[NMAX], ans, aux;
bitset<KMAX> dp[NMAX], oki;

void z_alg( string zstr ) {
    
    z[1] = 0;
    for( int i = 2, l = 1, r = 1; i <= zstr.length(); i ++ ) {
        if( i > r ) {
            int j = 1;
            while( i + j - 1 <= zstr.length() && zstr[j - 1] == zstr[i + j - 2] )
                j ++;
            
            z[i] = j - 1;
            l = i; r = i + z[i] - 1;
        }
        else {
            int ii = i - l + 1;
            
            if( z[ii] < r - i + 1 )
                z[i] = z[ii];
            else {
                int j = r - i + 1;
                while( i + j - 1 <= zstr.length() && zstr[j - 1] == zstr[i + j - 2] )
                    j ++;
                
                z[i] = j - 1;
                l = i; r = i + z[i] - 1;
            }
        }
    }
    
    for( int i = 1; i <= zstr.length(); i ++ ) {
        z[i - 1] = z[i];
        z[i] = 0;
    }
    
    return;
}

int main( void ) {
    ios::sync_with_stdio( false );
    
    int n, k;
    cin >> n >> k;
    
    for( int i = 1; i <= n; i ++ )
        cin >> str[i];
    
    dp[n + 1][0] = true;
    for( int i = n; i >= 1; i -- ) {
        dp[i] = dp[i + 1];
        
        for( int j = (int) str[i].length(); j <= k; j ++ )
            dp[i][j] = dp[i][j] | dp[i + 1][j - str[i].length()];
    }
    
    oki[0] = true;
    for( int i = 1; i <= n; i ++ ) {
        int l = (int) str[i].length(), pos = -1;
        pair<int, char> pr( k + 1, 'a' );
        
        aux = str[i] + '$' + ans;
        z_alg( aux );
        
        for( int j = 0; j <= min( (int) ans.length(), k - l ); j ++ ) {
            int p = z[j + 1 + l];
            
            if( oki[j] == false || dp[i + 1][k - j - l] == false )
                continue;
            if( p >= l || j + p >= ans.size() || str[i][p] >= ans[p + j] )
                continue;
            
            if( pr  > make_pair( j + p, str[i][p] ) ) {
                pr  = make_pair( j + p, str[i][p] );
                pos = j;
            }
            else
            if( pr == make_pair( j + p, str[i][p] ) ) {
                int q = z[j - pos];
                if( j - pos + q == str[i].length() || str[i][q] < str[i][j - pos + q] )
                    pos = j;
            }
        }
        
        if( pos != -1 ) {
            for( int j = pr.first + 1; j <= ans.size(); j ++ )
                oki[j] = false;
            
            ans.resize( pos ); ans += str[i];
            oki[ans.length()] = true;
        }
        else {
            for( int j = 0; j <= min( (int) ans.length(), k - l ); j ++ ) {
                int p = z[j + 1 + l];
                
                if( oki[j] == false || dp[i + 1][k - j - l] == false )
                    continue;
                
                if( j + p == ans.length() ) {
                    if( pos == -1 )
                        pos = j;
                    else {
                        int q = z[j - pos];
                        if( j - pos + q == str[i].length() || str[i][q] < str[i][j - pos + q] )
                            pos = j;
                    }
                }
            }
            
            if( pos != -1 ) {
                ans.resize( pos ); ans += str[i];
                oki[ans.length()] = true;
            }
        }
        
        aux = str[i] + '$' + ans;
        z_alg( aux );
        
        for( int j = min( (int) ans.length() - 1, k - l ); j >= 0; j -- ) {
            int p = z[j + 1 + l];
            
            if( oki[j] == false || dp[i + 1][k - j - l] == false )
                continue;
            
            if( p == l )
                oki[j + l] = true;
        }
    }
    
    cout << ans << endl;
    return 0;
}