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 modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000005

struct SA_IS{
	
	vector<int> a;
	vector<int> rank;
	vector<int> LCP;
	SA_IS(string &S){
		S.push_back('$');
		vector<int> n(S.size());
		
		map<int,int> mp;
		
		for(int i=0;i<S.size();i++){
			n[i] = encode(S[i]);
			mp[n[i]]=0;
		}
		
		int now = 0;
		for(auto &a:mp){
			a.second = now;
			now++;
		}
		
		for(int i=0;i<n.size();i++){
			n[i] = mp[n[i]];
		}
	
		a = suffix_array(n);
		
		rank.resize(a.size());
		for(int i=0;i<a.size();i++){
			rank[a[i]]=i;
		}
		
		LCP = build_LCP(n);
	}
	
	vector<int> suffix_array(vector<int> n){

		{
			vector<int> ret(n.size(),-1);
			bool f = true;
			for(int i=0;i<n.size();i++){
				if(ret[n[i]]!=-1){
					f=false;
					break;
				}
				ret[n[i]]=i;
			}
			if(f)return ret;
		}
		
		vector<bool> is_L(n.size(),false);
		vector<vector<int>> indices(n.size(),vector<int>());
		vector<int> l(n.size()),r(n.size());
		
		for(int i=n.size()-2;i>=0;i--){
			if(n[i]==n[i+1])is_L[i]=is_L[i+1];
			else if(n[i]>n[i+1])is_L[i]=true;
		}
		
		for(int i=0;i<n.size();i++){
			indices[n[i]].push_back(-1);
		}
		
		for(int i=0;i<n.size();i++){
			l[i] = 0;
			r[i] = indices[i].size();
		}
		
		for(int i=n.size()-1;i>=1;i--){
			if(!is_L[i]&&is_L[i-1]){
				r[n[i]]--;
				indices[n[i]][r[n[i]]]=i;
			}
		}
		
		
				
		induced_sort(n,is_L,indices,l,r);
				
		vector<int> LMSs;
		vector<int> fixedLMSs(n.size(),-1);
		for(int i=0;i<indices.size();i++){
			for(int j=0;j<indices[i].size();j++){
				int pos = indices[i][j];
				if(pos<=0)continue;
				if(is_L[pos-1]&&!is_L[pos]){
					fixedLMSs[pos]=LMSs.size();
					LMSs.push_back(pos);
				}
			}
		}

		vector<vector<int>> S(LMSs.size(),vector<int>());
		for(int i=0;i<S.size();i++){
			bool f = true;
			for(int j=LMSs[i];j<n.size();j++){
				if(is_L[j])f=false;
				else if(!f)break;
				S[i].push_back(n[j]);
			}
		}
		
		vector<int> new_n(S.size(),0);
		for(int i=1;i<S.size();i++){
			new_n[i] = new_n[i-1];
			if(S[i]!=S[i-1])new_n[i]++;
		}
		
		vector<int> t;
		vector<int> x;
		for(int i=0;i<n.size();i++){
			if(fixedLMSs[i]!=-1){
				t.push_back(new_n[fixedLMSs[i]]);
				x.push_back(i);
			}
		}
				
		new_n = suffix_array(t);
		
		for(int i=0;i<new_n.size();i++){
			LMSs[i] = x[new_n[i]];
		}
		
		for(int i=0;i<indices.size();i++){
			for(int j=0;j<indices[i].size();j++){
				indices[i][j]=-1;
			}
			l[i] = 0;
			r[i] = indices[i].size();
		}
		
		for(int i=LMSs.size()-1;i>=0;i--){
			int pos = LMSs[i];
			r[n[pos]]--;
			indices[n[pos]][r[n[pos]]]=pos;
		}
		
		induced_sort(n,is_L,indices,l,r);

		vector<int> ret;
		for(int i=0;i<indices.size();i++){
			for(int j=0;j<indices[i].size();j++)ret.push_back(indices[i][j]);
		}

		return ret;
		
	}
	
	void induced_sort(vector<int> &n,vector<bool> &is_L,vector<vector<int>> &indices,vector<int> &l,vector<int> &r){
		
		for(int i=0;i<indices.size();i++){
			for(int j=0;j<indices[i].size();j++){
				int pos = indices[i][j];
				if(pos<=0)continue;
				pos--;
				if(is_L[pos]){
					indices[n[pos]][l[n[pos]]]=pos;
					l[n[pos]]++;
				}
			}
		}
		
		for(int i=0;i<r.size();i++)r[i] = indices[i].size();
		
		for(int i=indices.size()-1;i>=0;i--){
			if(indices[i].size()==0)continue;
			for(int j=indices[i].size()-1;j>=0;j--){
				int pos = indices[i][j];
				if(pos<=0)continue;
				pos--;
				if(!is_L[pos]){
					r[n[pos]]--;
					indices[n[pos]][r[n[pos]]]=pos;
				}
			}
		}
		
	}
	
	vector<int> build_LCP(vector<int> n){
		
		vector<int> ret(a.size(),0);
		for(int i=0;i+1<a.size();i++){
			if(i==0||ret[rank[i-1]]==0){
				ret[rank[i]]=0;
			}
			else{
				ret[rank[i]]=ret[rank[i-1]]-1;
			}
			
			while(true){
				int x = i;
				int y = a[rank[i]-1];
				x += ret[rank[i]];
				y += ret[rank[i]];
				if(max(x,y)>=a.size())break;
				if(n[x]==n[y])ret[rank[i]]++;
				else break;
			}
		}
		return ret;
		
	}
	
	int encode(char c){
		if(c=='$')return 0;
		if(c=='Y')return 1;
		return c-'a'+28;
	}
	
};

template <typename T>
struct sparse_table{
	const T init_value = 1000000001;
	
	vector<T> v;
	int n;
	int sz;
	sparse_table(vector<T> &x){
		sz = x.size();
		for(int i=0;true;i++){
			if((1<<i)>sz){
				n = i;
				break;
			}
		}
		v.resize(sz*n,init_value);
		
		for(int i=0;i<sz;i++){
			v[i] = x[i];
		}
		
		for(int i=1;i<n;i++){
			for(int j=0;j<sz+1-(1<<i);j++){
				int temp = j+(1<<(i-1));
				v[i*sz+j] = func(v[(i-1)*sz+j],v[(i-1)*sz+temp]);
			}
		}
	}
	
	T query(int l,int r){
		int x = 31-__builtin_clz(r-l);
		return func(v[sz*x+l],v[sz*x+r-(1<<x)]);
	}
	
	T func(T a,T b){
		return min(a,b);
	}
};

int main(){
	
	int N,K;
	cin>>N>>K;
	
	vector<string> S(N);
	string T = "";
	vector<vector<int>> ind(N);
	for(int i=0;i<N;i++){
		cin>>S[i];
		T += S[i];
		T += 'Y';
		ind[i].resize(S[i].size());
	}

	SA_IS SA(T);

	sparse_table<int> ST(SA.LCP);
	
	int now = 0;
	vector<pair<int,int>> head(N);
	for(int i=0;i<N;i++){
		for(int j=0;j<S[i].size();j++){
			ind[i][j] = SA.rank[now];
			now++;
		}
		head[i] = make_pair(ind[i][0],i);
		now++;
	}

	sort(head.begin(),head.end());
	vector<int> head_order(N);
	for(int i=0;i<N;i++){
		head_order[head[i].second]=i;
	}
	

	vector<vector<bool>> dp(N+1,vector<bool>(K+1,false));
	dp[0][0] = true;
	for(int i=0;i<N;i++){
		int t = S[N-1-i].size();
		for(int j=0;j<=K;j++){
			if(!dp[i][j])continue;
			
			dp[i+1][j] = true;
			if(j+t>K)continue;
			dp[i+1][j+t]=true;
		}
	}
	
	vector<pair<int,int>> X;
	for(int i=0;i<N;i++){
		X.emplace_back(S[i].size(),i);
	}
	
	sort(X.rbegin(),X.rend());
	
	reverse(dp.begin(),dp.end());
	
	vector<int> ans(K+1,-2);
	ans[0] = -1;
	int minInd = 0,minPos = 100000;

	for(int i=0;i<K;i++){
		minPos++;
		if(ans[i]==-2)continue;
		for(int j=0;j<X.size();j++){
			int i0 = X[j].second;
			if(i0 <= ans[i])continue;
			int remain = K - (i+X[j].first);
			if(remain<0)continue;
			if(!dp[i0+1][remain])continue;
			if(S[minInd].size()<=minPos){
				ans[i+X[j].first] = i0;
				minInd = i0;
				minPos = 0;
			}
			else{
				int v0 = head[head_order[i0]].first;
				int v1 = ind[minInd][minPos];
				if(ST.query(min(v0,v1)+1,max(v0,v1)+1)>=min(S[i0].size(),S[minInd].size()-minPos)){
					if(ans[i+X[j].first]<0)ans[i+X[j].first]=i0;
					else ans[i+X[j].first] = min(ans[i+X[j].first],i0);
					
					if(S[i0].size() > S[minInd].size() - minPos){
						minInd = i0;
						minPos = 0;
					}
					
				}
				else{
					if(v0<v1){
						ans[i+X[j].first] = i0;
						minInd = i0;
						minPos = 0;
					}
				}
			}
		}
		if(minPos>=S[minInd].size())continue;
		for(int j=i+1;j<K;j++){
			if(ans[j]<0)continue;
			int i0 = ans[j];
			int pos0 = S[i0].size()-(j-i);
			if(i0==minInd&&pos0==minPos)continue;
			int v0 = ind[minInd][minPos];
			int v1 = ind[i0][pos0];
			
			if(ST.query(min(v0,v1)+1,max(v0,v1)+1)<min(S[i0].size()-pos0,S[minInd].size()-minPos)){
				ans[j] = -2;
			}
		}
	}

	string s = "";
	int Now = K;
	while(Now!=0){
		string t(S[ans[Now]].rbegin(),S[ans[Now]].rend());
		s += t;
		Now -= S[ans[Now]].size();
	}
	
	reverse(s.begin(),s.end());
	cout<<s<<endl;
	
	
	return 0;
}