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<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=2005;
const int MAXK=10005;
struct node
{
	int x,y;
	node(){}node(int _x,int _y){x=_x;y=_y;}
}A[MAXK],sta[MAXK];int tp;bool vis[MAXK];
char ans[MAXK],S[MAXN][MAXK],T[2*MAXK];int n,K,anslen,len[MAXN];
bitset<MAXK> bi[MAXN];
bool flag[MAXK];
int P[2*MAXK];
void exkmp(int L)
{
	P[1]=0;
	for(int i=2,R=0,pos=0;i<=L;i++)
	{
		if(i<=R)P[i]=min(P[i-pos+1],R-i+1);else P[i]=0;
		while(i+P[i]<=L&&T[i+P[i]]==T[P[i]+1])++P[i];
		if(i+P[i]-1>R)R=i+P[i]-1,pos=i;
	}
}
int cmp(node n1,node n2)//< -1 = 0 > 1
{
	if(!n1.y&&!n2.y)return 0;
	if(!n2.y)return -cmp(n2,n1);
	if(!n1.y)
	{
		if(n1.x<=n2.x)return 0;int L=P[n2.x+1+len[n2.y]];
		if(n2.x+L>=n1.x||L==len[n2.y]-1)return 0;
		return T[L+1]-'a'<T[n2.x+L+1+len[n2.y]]-'a'?1:-1;
	}
	if(n1.x>n2.x)return -cmp(n2,n1);
	int L=P[n1.x+1+len[n1.y]];
	if(L==len[n1.y]-1)return 0;
	if(n1.x+L<n2.x)return T[L+1]-'a'<T[n1.x+L+1+len[n1.y]]-'a'?-1:1;
	L=P[n2.x-n1.x+1];
	if(n2.x+L==n1.x+len[n1.y]-1)return 0;
	return T[L+1]-'a'<T[n2.x-n1.x+L+1]-'a'?1:-1;
}
bool operator <(node n1,node n2){return cmp(n1,n2)==-1;}
bool operator ==(node n1,node n2){return cmp(n1,n2)==0;}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	n=read();K=read();
	for(int i=1;i<=n;i++)scanf("%s",S[i]+1),len[i]=strlen(S[i]+1);bi[n+1][0]=1;
	for(int i=n;i>=1;i--)bi[i]=bi[i+1]|(bi[i+1]<<len[i]);
	if(!bi[1][K])return pr2(-1),0;
	flag[0]=1;
	for(int i=1;i<=n;i++)
	{
		if(!anslen)
		{
			anslen=len[i];
			for(int j=1;j<=len[i];j++)ans[j]=S[i][j];flag[len[i]]=1;++len[i];
			continue;
		}
		for(int j=1;j<=len[i];j++)T[j]=S[i][j];T[len[i]+1]='#';++len[i];
		for(int j=1;j<=anslen;j++)T[j+len[i]]=ans[j];exkmp(len[i]+anslen);
		memset(vis,0,sizeof(vis));int ll=len[i]-1;
		for(int j=0;j<=min(anslen+ll,K);j++)if(bi[i+1][K-j])
		{
			if(flag[j])vis[j]=1,A[j]=node(j,0);
			if(j>=ll&&flag[j-ll])
			{
				if(!vis[j])vis[j]=1,A[j]=node(j-ll,i);
				else A[j]=(A[j]<node(j-ll,i)?A[j]:node(j-ll,i));
			}
		}tp=0;
		for(int j=0;j<=K;j++)if(vis[j])
		{
			while(tp&&A[j]<sta[tp])--tp;
			if(!tp||A[j]==sta[tp])sta[++tp]=A[j];
		}assert(tp);
		anslen=sta[tp].x+len[sta[tp].y];if(sta[tp].y)--anslen;
		for(int j=1;j<len[sta[tp].y];j++)ans[j+sta[tp].x]=S[sta[tp].y][j];
		memset(flag,0,sizeof(flag));
		for(int j=1;j<=tp;j++)flag[sta[j].x+(sta[j].y?len[sta[j].y]-1:0)]=1;
		
//		for(int j=1;j<=anslen;j++)putchar(ans[j]);puts("");
	}
	assert(anslen==K);
	for(int i=1;i<=K;i++)putchar(ans[i]);
	return 0;
}