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 LL long long
#define pa pair<int,int>
const int Maxn=2010;
const int Maxk=10010;
const int inf=2147483647;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int n,k;
string s[Maxn];
int len[Maxn],sl[Maxn],l=0;
bool f[Maxn][Maxk];//第i~n个字符串能否拼成j长度的串 
struct Node
{
	int id,pos;
	Node(int _id=0,int _pos=0){id=_id,pos=_pos;}
}List[2][Maxn];
char ans[Maxk];int la=0;
int cnt[30];
int main()
{
	memset(f,false,sizeof(f));
	n=read(),k=read();
	for(int i=1;i<=n;i++)
	{
		cin>>s[i],len[i]=s[i].size();
		for(int j=0;j<len[i];j++)cnt[s[i][j]-'a']++;
	}
	int flag=0,w;
	for(int i=0;i<26;i++)
	if(cnt[i])
	{
		flag++;
		w=i;
	}
	if(flag==1)
	{
		for(int i=1;i<=k;i++)
		printf("%c",w+'a');
		return 0;
	}
	sl[n+1]=0;for(int i=n;i;i--)sl[i]=sl[i+1]+len[i];
	f[n+1][0]=true;
	for(int i=n;i;i--)
	for(int j=0;j<=min(k,sl[i]);j++)
	{
		f[i][j]=f[i+1][j];
		if(j>=len[i])f[i][j]|=f[i+1][j-len[i]];
//		printf("%d %d %d\n",i,j,f[i][j]);
	}
	int now=0;
	for(int i=1;i<=n;i++)
	if(f[i+1][k-len[i]])List[now][++l]=Node(i,0);
	for(int i=1;i<=k;i++)
	{
//		printf("%d %d\n",i,l);
		int mn=inf;
		for(int j=1;j<=l;j++)
		{
			int id=List[now][j].id,pos=List[now][j].pos;
			mn=min(mn,(int)s[id][pos]);
		}
		ans[++la]=mn;//printf("%d ",mn);
		int tl=0,st=inf;
		for(int j=1;j<=l;j++)
		{
			int id=List[now][j].id,pos=List[now][j].pos;
			if(s[id][pos]!=mn)continue;
			if(pos+1!=len[id])List[now^1][++tl]=Node(id,pos+1);
			else st=min(st,id+1);
		}
		for(int j=st;j<=n;j++)
		if(len[j]<=k-i&&f[j+1][k-i-len[j]])List[now^1][++tl]=Node(j,0);
		l=tl;now^=1;
	}
//	printf("\nla=%d\n",la);
	for(int i=1;i<=la;i++)printf("%c",ans[i]);
}