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;

typedef pair<int,int> P;
typedef bitset<20010> B;

string S;
int sa[1000010][15];
void sa_init(){
	if(true){
		vector<P> vec;
		for(int i = 0 ; i < S.size() ; i ++){
			vec.push_back(P(S[i],0));
		}
		sort(vec.begin(),vec.end());
		for(int i = 0 ; i < S.size() ; i ++){
			sa[i][0] = lower_bound(vec.begin(),vec.end(),P(S[i],0)) - vec.begin();
		}
	}
	for(int t = 1 ; t < 14 ; t ++){
		vector<P> vec;
		for(int i = 0 ; i < S.size() ; i ++){
			if(i+(1<<(t-1)) < S.size())vec.push_back(P(sa[i][t-1],sa[i+(1<<(t-1))][t-1]));
			else vec.push_back(P(sa[i][t-1],-1));
		}
		sort(vec.begin(),vec.end());
		for(int i = 0 ; i < S.size() ; i ++){
			if(i+(1<<(t-1)) < S.size()){
				sa[i][t] = lower_bound(vec.begin(),vec.end(),P(sa[i][t-1],sa[i+(1<<(t-1))][t-1]))-vec.begin();
			}
			else {
				sa[i][t] = lower_bound(vec.begin(),vec.end(),P(sa[i][t-1],-1)) - vec.begin();
			}
		}
	}
}

int comp(int x,int y,int len,int t){
	if(len == 0)return 0;
	if(len < (1<<t))return comp(x,y,len,t-1);
	if(sa[x][t] == sa[y][t])return comp(x+(1<<t),y+(1<<t),len-(1<<t),t-1);
	else {
		if(sa[x][t] < sa[y][t])return 1;
		else return -1;
	}
}

int main(){
	static int n,k;
	static string s[2002];
	/*	srand((unsigned)time(NULL));
	while(1){
		n = rand()%4 + 1;
		k = (rand()%5 + 1)*2;
		vector<int> vec;
		int k_ = k;
		int n_ = n;
		while(k_ > 0){
			if(n_ == 1)vec.push_back(k_);
			else vec.push_back(rand()%100*2%k_+2);
			k_ -= vec[vec.size()-1];
			n_ --;
		}
		for(int i = 0 ; i < n_ ; i ++){
			vec.push_back(rand()%k + 1);
		}
		random_shuffle(vec.begin(),vec.end());
		for(int i = 1 ; i <= n ; i ++){
			s[i] = "";
			for(int j = 0 ; j < vec[i-1] ; j ++){
				if(j&1)s[i] += "a";
				else s[i] += "b";
			}
		}*/
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++){
		cin >> s[i];
	}
	
	S = "";
	for(int i = 1 ; i <= n ; i ++){
		S += s[i];
	}
	sa_init();
	
	static B ok_l[2002], ok_r[2002], ok[2002];
	ok_l[0].reset(); ok_l[0][0] = true;
	for(int i = 1 ; i <= n ; i ++){
		ok_l[i] = ok_l[i-1] | (ok_l[i-1]<<(s[i].size()));
	}
	ok_r[n].reset(); ok_r[n][k] = true;
	for(int i = n ; i >= 1 ; i --){
		ok_r[i-1] = ok_r[i] | (ok_r[i]>>(s[i].size()));
	}
	for(int i = 1 ; i <= n ; i ++){
		ok[i] = ok_l[i] & ok_r[i];
	}
	
	/*for(int i = 1 ; i <= n ; i ++){
		for(int j = 0 ; j <= 20 ; j ++){
			if(ok_r[i][j])printf("1");
			else printf("0");
		}
		cout << endl;
	}*/
	
	string ret(k,'z'+1);
	B start[2];
	int t=0,t_=1;
	start[t].reset(); start[t][0] = true;
	int sum = 0;
	for(int i = 1 ; i <= n ; i ++){
		start[t_].reset(); if(ok[i][0])start[t_][0] = true;
		deque<int> deq;
		for(int j = 1 ; j <= k ; j ++){
			if(start[t][j-1] && ok[i][j+s[i].size()-1]){
				while(deq.size()>0){
					int r = comp(sum,sum+j-deq.back(),s[i].size()-(j-deq.back()),14);
					//cout << "r=" << r << endl;
					if(r == 1)deq.pop_back();
					else if(r == 0){
						deq.push_back(j);
						break;
					}
					else break;
				}
				if(deq.size() == 0)deq.push_back(j);
			}
			/*for(int x: deq){
				cout << x << " ";
			}
			cout << endl;*/
			if(deq.size() > 0){
				char c = s[i][j-deq.back()];
				if(ret[j-1] < c){
					deq.clear();
				}
				else if(ret[j-1] == c){}
				else {
					for(int x = 0 ; x < s[i].size() ; x ++){
						ret[deq.back()-1+x] = s[i][x];
					}
					if(deq.back()-1+s[i].size() < k)ret[deq.back()-1+s[i].size()] = 'z'+1;
					while(deq.size()>0){
						start[t_][deq.back()+s[i].size()-1] = true;
						deq.pop_back();
					}
					break;
				}
				if(deq.size() > 0 && deq.front() == j-s[i].size()+1){
					start[t_][j] = true;
					deq.pop_front();
				}
			}
			if(start[t][j] && ok[i][j])start[t_][j] = true;
			/*for(int x: deq){
				cout << x << " ";
			}
			cout << endl;*/
		}
		swap(t,t_);
		sum += s[i].size();
		
		/*cout << ret << endl;
		for(int j = 0 ; j <= 20 ; j ++){
			if(start[t][j])printf("1");
			else printf("0");
		}cout << endl;*/
	}
	cout << ret << endl;
	/*	bool aa = true;
		for(int i = 0 ; i < ret.size() ; i ++){
			if((i&1) && ret[i] != 'a')aa = false;
			if(!(i&1) && ret[i] != 'b')aa = false;
		}
		if(!aa){
			cout << n << " " << k << endl;
			for(int i = 1 ; i <= n ; i ++){
				cout << s[i] << endl;
			}
			cout << ret << endl;
			break;
		}
		puts("ok");
	}*/
}