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:
//pragma
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define YOU using
#define DONT namespace
#define SAY std

YOU DONT SAY;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define REPP(i,a,b,d) for(int i=a;i<=b;i+=d)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,d) for(int i=a;i>=b;i-=d)
#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) for(int i=0; i<a; i++)
#define FORD(i,a) for(int i=(int)a-1; i>=0; i--)

#define pb push_back
#define F first
#define S second

const int OO = 1e9;
const ll INF = 1e18;

const int irand(int lo,int hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

const ll lrand(ll lo,ll hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

#define getc getchar
template<typename T>
T getnum(){
	int sign = 1;
	T ret = 0;
	char c;

	do{
		c = getc();
	}while(c == ' ' || c == '\n');
	if(c == '-')sign = -1;
	else ret = c-'0';
	while(1){
		c = getc();
		if(c < '0' || c > '9')break;
		ret = 10*ret + c-'0';
	}
	return sign * ret;
}

inline void ini(int& x){
	x = getnum<int>();
}

inline void scani(int& x){
	scanf("%d",&x);
}

//end of macro

int n, k;
string str[2000];

int memo1[2000][10005];
int dp1(int now, int len){ // returns 1 if reach end, 0 otherwise
	if(now == n){
		return len == k;
	}

	int& ret = memo1[now][len];
	if(ret != -1)return ret;

	ret = dp1(now+1, len);
	if(len+str[now].size() <= k)ret |= dp1(now+1, len+str[now].size());
	return ret;
}

bool dp2[2005][10005];

// Z[i] = LCP of string s[0..N] and s[i..N]
int Z[20005];
void buildZ(string s){
	int l,r;
	l = r = 0;
	Z[0] = s.size();
	for(int i = 1; i < s.size(); i++) {
	    if(i > r) { // over bound -> manual widen
	        l = r = i;
	        while(r < s.size() && s[r-l] == s[r]) r++;
	        Z[i] = r-l; r--;
	    }else{
	        if(Z[i-l] < r-i+1) Z[i] = Z[i-l];
	        else{ // lcp exceeds bound -> manual widen
	            l = i;
	            while(r < s.size() && s[r-l] == s[r]) r++;
	            Z[i] = r-l; r--;
	        }
	    }
	}
	Z[s.size()] = 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #define endl '\n'
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(10);

    cin>>n>>k;
    FOR(i,n){
    	cin>>str[i];
    }

    memset(memo1, -1, sizeof memo1);

    string ans;
    dp2[0][0] = 1;
    FOR(i,n){
    	buildZ(str[i] + ans);

    	int right_lim = k;
    	int best = -1;
    	REP(j,0,k){
    		if(j <= right_lim && dp2[i][j] == 1){
    			dp2[i+1][j] = 1; // not adding str[i];

    			if(j+str[i].size() <= k && dp1(i+1, j+str[i].size())){
    				// adding str[i] can still reach end
    				int lcp = (j == ans.size()) ? 0 : Z[str[i].size() + j]; // lcp of str[i][0] and ans[j]
    				if(best != -1)lcp = Z[j - best]; // ans is already updated
    				if(lcp >= str[i].size()){ // adding str[i] won't do anything
    					dp2[i+1][j+str[i].size()] = 1;
    				}else if(lcp < str[i].size()){
    					if(lcp+j < ans.size() && str[i][lcp] > ans[lcp+j]){ // adding results in worse
    						// well, do nothing
    					}else{ // better result
    						dp2[i+1][j+str[i].size()] = 1;
    						right_lim = min(right_lim, j + lcp);

    						if(best != -1 && lcp+j < ans.size())dp2[i+1][best+str[i].size()] = 0;
    						best = j;
    						ans = ans.substr(0, best) + str[i];
    					}
    				}
    			}
    		}
    	}
    }

    assert(ans.size() == k);

    // printf("size ans %d, k %d\n",ans.size(),k);

    cout << ans << endl;

    return 0;
}