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<stdio.h>
#include<algorithm>
#include<string>
#include<vector>
#include<string.h>
using namespace std;
int R=10;
string s[2100];
char in[11000];
typedef unsigned long long wolf;
wolf rj[11000];
wolf ks=1000000007;
char rd[2010][10010];
char dp[2010][10010];
char st[2010][10010];
vector<wolf> Hash[2010];
wolf cur[10010];
int lc[10100];
int f[]={114,514,810,1919,893,364364,334,1000000007,31415926,1145141919};
inline bool eq(int a,int b,int c,int d){
	int len=b-a;
//	printf("%d %d %d: %llu %llu %llu %llu\n",a,b,c,cur[b]-cur[a],Hash[c][len],rj[a],Hash[c][len]*rj[a]);
	if(cur[b]-cur[a]!=Hash[c][len]*rj[a])return false;
	for(int i=0;i<R;i++){
		int at=f[i]%len;
		if(st[d][a+at]!=s[c][at]){
		//	printf("%d\n",i);
			return false;
		}
	}
	return true;
}
inline int calc(int a,int b){
	if(eq(a,a+s[b].size(),b,b))return 9999999;
	int left=a-1;
	int right=a+s[b].size();
	while(left+1<right){
		int M=(left+right)/2;
		if(eq(a,M+1,b,b)){
			left=M;
		}else right=M;
	}
	//printf("%d\n",right);
	//if(right==a+s[b].size())return 0;
	//if(s[b][right-a]<st[b][right])return 1;
	//return -1;
	return right;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%s",in);
		s[i]=in;
	}
	rj[0]=1;
	for(int i=1;i<11000;i++)rj[i]=rj[i-1]*ks;
	rd[a][b]=1;
	for(int i=a;i;i--){
		for(int j=0;j<=b;j++){
			if(rd[i][j]&&j>=s[i-1].size()){
				rd[i-1][j-(int)(s[i-1].size())]=1;
			}
			if(rd[i][j])rd[i-1][j]=1;
		}
	}
	for(int i=0;i<a;i++){
		Hash[i]=vector<wolf>(s[i].size()+1);
		wolf now=0;
		wolf tt=1;
		for(int j=0;j<s[i].size();j++){
			now+=tt*s[i][j];
			tt*=ks;
			Hash[i][j+1]=now;
	//		printf("%llu ",now);
		}
	//	printf("\n");
	}
	dp[0][0]=1;
	for(int i=0;i<b;i++)st[0][i]='~';
	for(int i=0;i<a;i++){
		wolf now=0;
		wolf tt=1;
		for(int j=0;j<b;j++){
			now+=tt*st[i][j];
			tt*=ks;
			cur[j+1]=now;
		//	printf("%llu ",now);
		}
		//printf("\n");
		for(int j=0;j<=b;j++)st[i+1][j]=st[i][j];
	//	if(i==1561)printf("%s\n",st[i]);
		int lcp=b;
		int bv=-1;
		for(int j=0;j<=b;j++){
			if(!dp[i][j])continue;
			if(j+s[i].size()<=b&&rd[i+1][j+s[i].size()]){
				int val=calc(j,i);
				lc[j]=val;
				if(bv==-1){
					if(val<b&&s[i][val-j]<st[i][val]){
						bv=j;
						lcp=lc[j];
					}
				}else{
					if((val<lc[bv]&&s[i][val-j]<st[i][val])||(val==lc[bv]&&s[i][val-j]<=s[i][lc[bv]-bv])){
						bv=j;
						lcp=lc[j];
					}
				}
				
			}
		}
	//	if(i==1560)printf("%d %d\n",bv,lcp);
		if(bv!=-1){
			for(int j=bv;j<bv+s[i].size();j++)st[i+1][j]=s[i][j-bv];
			for(int j=bv+s[i].size();j<b;j++)st[i+1][j]='~';
		}
		//printf("%s\n",st[i+1]);
		now=0;
		tt=1;
		for(int j=0;j<b;j++){
			now+=tt*st[i+1][j];
			tt*=ks;
			cur[j+1]=now;
		//	printf("%llu ",now);
		}
		for(int j=0;j<=b;j++){
			if(!dp[i][j])continue;
	//		printf("%d %d\n",i,j);
			if(j+s[i].size()<=b&&lcp>=j&&rd[i+1][j+s[i].size()]){
				if(eq(j,j+s[i].size(),i,i+1))dp[i+1][j+s[i].size()]=1;
			}
			if(rd[i+1][j]&&j<=lcp){
				dp[i+1][j]=1;
		//		if(i>1550)printf("%d %d\n",i,j);
			}
		}
	}
	printf("%s\n",st[a]);
}