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>
#define N 2009
#define M 10009
using namespace std;
 
int n,m,len,cnt,a[N],q[M],f[M<<1];
char s[N][M],ch[M],s0[M<<1]; bool bo[N][M],ok[M],vis[M];
struct node{ int x,y; }b[M];
int sig(node u,node v){
	if (!u.y && !v.y) return 0;
	if (!u.y) return -sig(v,u);
	if (!v.y){
		if (v.x<=u.x) return 0;
		int t=f[u.x+u.y+1];
		if (u.x+t>=v.x) return 0; else
		return s0[t+1]<s0[u.x+u.y+t+1]?-1:1;
	}
	if (u.x==v.x) return 0;
	if (u.x>v.x) return -sig(v,u);
	int t=f[u.x+u.y+1];
	if (u.x+t>=v.x){
		t=v.x-u.x;
		if (f[t+1]>=u.y-t) return 0;
		else return s0[f[t+1]+t+1]<s0[f[t+1]+1]?-1:1;
	} else return s0[t+1]<s0[u.x+u.y+t+1]?-1:1;
}
bool operator <(node u,node v){ return sig(u,v)<0; }
bool operator ==(node u,node v){ return !sig(u,v); }
void work(char *s,int n){
	int i,k; f[1]=0;
	for (i=2,k=1; i<=n; i++){
		f[i]=min(k+f[k]-i,f[i-k+1]);
		if (f[i]<0) f[i]=0;
		for (; s[f[i]+1]==s[i+f[i]] && i+f[i]<=n; f[i]++);
		if (i+f[i]>k+f[k]) k=i;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	int i,j,k;
	for (i=1; i<=n; i++){
		scanf("%s",s[i]+1); a[i]=strlen(s[i]+1);
	}
	bo[n+1][0]=1;
	for (i=n; i; i--){
		for (j=m; j>=0; j--){
			bo[i][j]=bo[i+1][j];
			if (j>=a[i]) bo[i][j]|=bo[i+1][j-a[i]];
		}
	}
	ok[0]=1; len=0;
	for (i=1; i<=n; i++){
		if (!len){
			if (bo[i+1][m-a[i]]){
				len=a[i];
				for (j=1; j<=len; j++) ch[j]=s[i][j];
			}
			ok[len]=1; continue;
		}
		for (j=1; j<=a[i]; j++) s0[j]=s[i][j];
		for (j=1,cnt=a[i]; j<=len; j++) s0[++cnt]=ch[j];
		work(s0,cnt);
		memset(vis,0,sizeof(vis));
		for (j=0; j<=m; j++) if (bo[i+1][m-j]){
			if (ok[j]){
				vis[j]=1; b[j]=(node){j,0};
			}
			if (j>=a[i] && ok[j-a[i]])
				if (vis[j]) b[j]=min(b[j],(node){j-a[i],a[i]}); else{
					vis[j]=1;
					b[j]=(node){j-a[i],a[i]};
				}
		}
		q[1]=0;
		for (j=k=1; j<=m; j++) if (vis[j]){
			while (k>1 && b[j]<b[q[k]]) k--;
			if (b[j]==b[q[k]]) q[++k]=j;
		}
		len=q[k];
		if (b[len].y)
			for (j=1; j<=a[i]; j++) ch[b[len].x+j]=s[i][j];
		ch[len+1]=0;
		memset(ok,0,sizeof(ok));
		while (k) ok[q[k--]]=1;
	}
	printf("%s\n",ch+1);
	return 0;
}