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<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
bool dp[2016][10010],d2[2016][10010];
string s[2016],t[2016];
int len[2016];
vector<int> za;
vector<int> zalgo(string s){
	int i=1,j=0,n=s.size();
	vector<int> a(n,0);
	a[0]=n;
	while(i<n){
		while(i+j<n && s[j]==s[i+j]) j++;
		a[i]=j;
		if(j==0){i++;continue;}
		int k=1;
		while(i+k<n && k+a[k]<j){a[i+k]=a[k];++k;}
		i+=k;j-=k;
	}
	return a;
}

//T[0~be]とT[0~j]+Sを比較
int cal(int i,int be,int j){
	if(be<=j) return 0;
	int ma=za[j+len[i]];ma=min(ma,min(be-j,len[i]));
	if(ma==min(be-j,len[i])) return 0;
	else if(s[i][ma]<t[i][j+ma]) return 1;return -1;
}

//T[0~be]+SとT[0~j]+Sを比較
int cal2(int i,int be,int j){
	if(be>j) return -cal2(i,j,be);
	if(be==j) return 0;
	int ma=za[len[i]+be];
	if(ma<j-be){
		if(t[i][ma+be]<s[i][ma]) return 1;return -1;
	}
	ma=za[j-be];
	//if(i==2 && be==3 && j==4) cout<<ma<<endl;cout<<s[ma]<<' '<<
	if(ma>=len[i]-j+be) return 0;
	else if(s[i][ma]<s[i][ma+j-be]) return 1;return -1;
}
int main()
{
	int n,k;
	cin>>n>>k;
	memset(dp,false,sizeof(dp));dp[n][k]=true;
	rep(i,n){
		cin>>s[i];len[i]=s[i].size();
	}
	for(int i=n;i>0;i--) rep(j,k+1){
		if(!dp[i][j]) continue;
		if(j>=len[i-1]) dp[i-1][j-len[i-1]]=true;
		dp[i-1][j]=true;
	}
	/*rep(i,n) rep(j,k+1){
		if(dp[i][j]) cout<<i<<' '<<j<<endl;
	}*/
	rep(i,n) t[i]="";
	memset(d2,false,sizeof(d2));d2[0][0]=true;
	rep(i,n){
		//cout<<t[i]<<endl;rep(j,t[i].size()+1){if(d2[i][j]) cout<<j<<' ';}cout<<endl;
		za=zalgo(s[i]+t[i]);
		int be=-1;
		rep(j,t[i].size()+1){
			if(j+len[i]>k || !dp[i+1][j+len[i]] || !d2[i][j]) continue;
			if(be<0){
				int x=cal(i,t[i].size(),j);
				if(x>0 || (x==0 && j+len[i]>t[i].size())) be=j;
			}
			else{
				int x=cal2(i,be,j);
				if(x>=0) be=j;
			}
		}
		rep(j,t[i].size()+1){
			if(!d2[i][j]) continue;
			if(dp[i+1][j]){
				if(be<0) d2[i+1][j]=true;
				else{
					if(cal(i,j,be)<=0) d2[i+1][j]=true;
					//if(cal(i,j,be)<0) while(1){}
				}
			}
			if(j+len[i]>k || !dp[i+1][j+len[i]]) continue;
			if(be<0){
				if(cal(i,t[i].size(),j)>=0) d2[i+1][j+len[i]]=true;
				//if(cal(i,t[i].size(),j)>0) while(1){}
			}
			else{
				if(cal2(i,be,j)>=0) d2[i+1][j+len[i]]=true;
				//if(cal2(i,be,j)>0) while(1){}
			}
		}
		if(be<0) t[i+1]=t[i];
		else t[i+1]=t[i].substr(0,be)+s[i];
	}
	cout<<t[n]<<endl;
}