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<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<sstream>
#include<numeric>
#include<iostream>
#include<algorithm>
#include<functional>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> Vi;
typedef pair<int,int> pii;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=2000+19;
const int K=10000+19;

const int p=1e9+7;

bitset<K> G[N],F[N];
string s[N],t[N];
int pw[K];
Vi ht[N],hs[N];
int n,k,nx,ny;
char str[K];

void Upd(int i,int x,int y){
	if (!F[i-1][x]) return;
	if (!nx&&!ny){
		nx=x,ny=y;
		F[i][x+y]=1;
		return;
	}
	int l=0,r=x+y;
	while (l<=r){
		int mid=(l+r>>1),las=0,cur=0;
		cur=(mid<=x?ht[i-1][mid]:(ht[i-1][x]+1ll*pw[x]*hs[i][mid-x])%p);
		las=(mid<=nx?ht[i-1][mid]:(ht[i-1][nx]+1ll*pw[nx]*hs[i][mid-nx])%p);
		if (cur==las) l=mid+1;else r=mid-1;
	}
	if (l-1==x+y){
		F[i][x+y]=1;
		return;
	}
	int ccur,clas;
	ccur=(l<=x?t[i-1][l-1]:s[i][l-x-1]);
	clas=(l<=nx?t[i-1][l-1]:s[i][l-nx-1]);
	if (ccur<clas){
		nx=x,ny=y;
		F[i][x+y]=1;
	}
	/*
	string cur=t[i-1].substr(0,x)+s[i].substr(0,y);
	string las=t[i-1].substr(0,nx)+s[i].substr(0,ny);
	if (las.substr(0,cur.length())==cur){
		F[i][x+y]=1;
		return;
	}
	if (cur<las){
		nx=x,ny=y;
		F[i][x+y]=1;
	}
	*/
}

int main(){
	pw[0]=1;
	For(i,1,K) pw[i]=23ll*pw[i-1]%p;
	n=IN(),k=IN();
	For(i,1,n+1){
		scanf("%s",str);
		s[i]=string(str);
	}
	For(i,0,n+1){
		hs[i].pb(0);
		For(j,0,s[i].length()){
			hs[i].pb((hs[i].back()+1ll*pw[j]*(s[i][j]-'a'))%p);
		}
	}
	G[n+1][0]=1;
	for (int i=n;i;i--){
		G[i]=G[i+1]|(G[i+1]<<s[i].length());
	}
	if (!G[1][k]){
		puts("QAQ");
		return 0;
	}
	F[0][0]=1;
	ht[0].pb(0);
	For(i,1,n+1){
		nx=0,ny=0;
		for (int j=k;~j;j--)
			if (G[i+1][k-j]){
				Upd(i,j,0);
				if (j>=s[i].length()){
					Upd(i,j-s[i].length(),s[i].length());
				}
			}
		For(j,0,nx) t[i]+=t[i-1][j];
		For(j,0,ny) t[i]+=s[i][j];
		ht[i].pb(0);
		For(j,0,t[i].length()){
			ht[i].pb((ht[i].back()+1ll*pw[j]*(t[i][j]-'a'))%p);
		}
		For(j,t[i].length()+1,k+1) F[i][j]=0;
	}
	puts(t[n].c_str());
}