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<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<cmath>
#include<string>

#define ls (t<<1)
#define rs ((t<<1)+1)
#define mid ((l+r)>>1)
#define fi first
#define se second
#define mk make_pair
#define pb push_back

#define N 2005
#define M 10005
#define seed 23333

using namespace std;
const int inf=(int)1e9;
int i,j,m,n,p,k,len[N],now,last,K;
bitset<M>can[N];
vector<int>Next[N];
string c[N];
int g[2][M],f[M],sz[M];
string d;
int used[M];
pair<int,int> r[M];
void get_Next(int x)
{
		int a=1,i,j;
		Next[x].pb(len[x]);
		for (j=1;j<len[x];++j) if (c[x][j-1]!=c[x][j]) break;
		Next[x].pb(j-1);
		for (i=2;i<len[x];++i)
		{
			   int p=a+Next[x][a]-1,L=Next[x][i-a];
			   if (i+L-1<p) Next[x].pb(L);
			   else 
			   {
			   		int now;
			   		if (i>p) now=0; else now=p-i+1;
			   		while (i+now<len[x]&&c[x][i+now]==c[x][now]) ++now;
			   		Next[x].pb(now);
			   		a=i;
			   }
		}
}
void Extend(int x)
{
		memset(used,0,sizeof(used));
		int Len=d.length(),Min=min(Len,len[x]);
		if (!Min) return;
		int a=0,i,j;
		for (j=0;j<Min;++j) if (d[j]!=c[x][j]) break;
		used[0]=j;
		for (i=1;i<Len;++i)
		{
			   if (i==43)
			   		i=43;
			   int p=a+used[a]-1,L=Next[x][i-a];
			   if (i+L-1<p) used[i]=L;
			   else 
			   {
			   		int now;
			   		if (i>p) now=0; else now=p-i+1;
			   		while (i+now<Len&&now<len[x]&&d[i+now]==c[x][now]) ++now;
			   		used[i]=now;
			   		a=i;
			   }
		}
}
int check(pair<int,int> x,pair<int,int> y)
{
		if (x.fi<=y.fi)
		{
				if (x.se==0) return 2;
				if (used[x.fi]>=y.fi-x.fi)
				{
						if (y.se==0) return 2;
						int p=Next[i][y.fi-x.fi];
						if (p>=len[i]-(y.fi-x.fi)) return 2;
						else return c[i][y.fi-x.fi+p]<c[i][p]; 	
				}
				else if (used[x.fi]==len[i]) return 2;
				else return c[i][used[x.fi]]<d[x.fi+used[x.fi]];
		}
		else 
		{
				if (y.se==0) return 2;
				if (used[y.fi]>=x.fi-y.fi)
				{
						if (x.se==0) return 2;
						int p=Next[i][x.fi-y.fi];
						if (p>=len[i]-(x.fi-y.fi)) return 2;
						else return c[i][p]<c[i][x.fi-y.fi+p];
				}
				else if (used[y.fi]==len[i]) return 2;
				else return d[y.fi+used[y.fi]]<c[i][used[y.fi]];
		}
}
void Ins(int x,int y)
{
		if (!can[i+1][K-x-y*len[i]]) return;
		while (sz[now])
		{
				int gg=check(r[sz[now]],mk(x,y));
				if (gg==2)
				{
					if (g[now][sz[now]]==x+y*len[i]) return;
					g[now][++sz[now]]=x+y*len[i];
					r[sz[now]]=mk(x,y);
					return;
				}
				else if (gg==1) return; 
				else --sz[now];
		}
		g[now][++sz[now]]=x+y*len[i];
		r[sz[now]]=mk(x,y); 
}
int main()
{
	scanf("%d%d",&n,&K);
	for (i=1;i<=n;++i)	cin>>c[i],len[i]=c[i].length(),get_Next(i);
	can[n+1][0]=1;
	for (i=n;i;--i) can[i]=can[i+1]|(can[i+1]<<len[i]);
	if (!can[1][K])
	{
			puts("cao");
			return 0;
	}
	g[0][++sz[0]]=0;
	for (i=1;i<=n;++i)
	{
			now^=1; last=now^1;
			Extend(i);
			sz[now]=0;
			for (j=1,f[0]=0;j<=sz[last]&&g[last][j]+len[i]<=K;++j) 
				f[++f[0]]=g[last][j];
			int ll=1,rr=1;
			g[last][sz[last]+1]=inf;
			f[f[0]+1]=inf;
			while (ll<=sz[last]||rr<=f[0])
			{
					if (rr>f[0]) Ins(g[last][ll],0),++ll;
					else if (ll>sz[last]) Ins(f[rr],1),++rr;
					else if (g[last][ll]<=f[rr]+len[i]) Ins(g[last][ll],0),++ll;
					else Ins(f[rr],1),++rr;	
			}
			string e;
			for (j=1;j<=r[sz[now]].fi;++j) e+=d[j-1];
			if (r[sz[now]].se==1)
			e+=c[i];
			d=e;
	}
	cout<<d<<endl;
}