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 <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <time.h>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
const int mod=1e9+7;
using namespace std;
int n,k;
int len[2005];
string str[2005];
int f[2005][10005];
string cur;
int curH[10005];
int e[10005];
bool ok[10005];
int strH[10005];
int var;
int opti;

inline int gethash(int h[],int l,int r)
{
	if(r==0) return 0;
	opti=h[r-1]-1LL*(l?h[l-1]:0)*e[r-l]%mod;
	return (opti<0?opti+mod:opti);
}

inline void init(string &c,int h[])
{
	int len=c.size();
	h[0]=c[0];
	for(int i=1;i<len;i++)
	{
		h[i]=(1LL*h[i-1]*107+c[i])%mod;
	}
}

bool dfs(int x,int y)
{
	if(y<0) return false;
	if(x==n) return (y==0);
	if(f[x][y]!=-1) return f[x][y];
	f[x][y]=dfs(x+1,y-len[x]) | dfs(x+1,y);
	return f[x][y];
}

inline bool same(const pii &a,const pii &b,int l)
{
	//1. ¶¼ÔÚÁ½¸öµÄid·¶Î§ÄÚ
	if(l<=a.first && l<=b.first)
	{
		return true;
	}
	//2. ÔÚaµÄid·¶Î§ÄÚ£¬ÔÚbµÄstr[var]ÄÚ(ËµÃ÷b.second==1)
	if(l<=a.first)
	{
		if(gethash(curH,b.first,l)==gethash(strH,0,l-b.first)) return true;else return false;
	}
	//3. ÔÚbµÄid·¶Î§ÄÚ¡£
	if(l<=b.first)
	{
		if(gethash(curH,a.first,l)==gethash(strH,0,l-a.first)) return true;else return false;
	}
	//4. ¶¼ÔÚ·¶Î§Íâ
	/*
	____--
	__--
	*/
	if(a.first>b.first)
	{
		if(gethash(curH,b.first,a.first)!=gethash(strH,0,a.first-b.first)) return false;
		if(gethash(strH,0,b.first+len[var]-a.first)!=gethash(strH,a.first-b.first,len[var])) return false;
		return true;
	}
	else
	{
		if(gethash(curH,a.first,b.first)!=gethash(strH,0,b.first-a.first)) return false;
		if(gethash(strH,0,a.first+len[var]-a.first)!=gethash(strH,b.first-a.first,len[var])) return false;
		return true;
	}
}

bool compare(const pii &a,const pii &b)
{
	int len1=a.first+a.second*len[var];
	int len2=b.first+b.second*len[var];
	int l=min(a.first,b.first),r=min(len1,len2),mid,res=-1;
	if(l==r) a.first<b.first;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(same(a,b,mid))
		{
			res=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	if(res==min(len1,len2)) return len1>len2;
	if(res>=a.first && res>=b.first)
	{
		return str[var][res-a.first]<str[var][res-b.first];
	}
	if(res>=a.first)
	{
		return str[var][res-a.first]<cur[res];
	}
	if(res>=b.first)
	{
		return cur[res]<str[var][res-b.first];
	}
}

bool check(pii a,pii b)
{
	int len1=a.first+a.second*len[var];
	int len2=b.first+b.second*len[var];
	int l=min(a.first,b.first),r=min(len1,len2),mid,res=-1;
	if(len2>len1) return false;
	if(l==r) return true;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(same(a,b,mid))
		{
			res=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	if(res==min(len1,len2)) return true;
	return false;
}

int main()
{
//	freopen("abab0.in","r",stdin);
	ios_base::sync_with_stdio(false);
	e[0]=1;
	memset(f,-1,sizeof(f));
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	{
		e[i]=(1LL*e[i-1]*107)%mod;
	}
	for(int i=0;i<n;i++)
	{
		cin>>str[i];
		len[i]=str[i].size();
	}
	cur="";
	ok[0]=true;
	vector <pair<int,int> >vec;
	double time;
	double SortUse;
	int size=0;
	pii optimization;
	for(int i=0;i<n;i++)
	{
//		if(i%10==0)
//		{
//			cout<<i<<endl;
//			cout<<SortUse/CLOCKS_PER_SEC<<endl;
//			cout<<size<<endl;
//			SortUse=0;
//			size=0;
//		}
		vec.clear();
		var=i;
		init(str[i],strH);
		for(int pos=cur.size();pos>=0;pos--)
		{
			if(!dfs(i,k-pos) || !ok[pos]) continue;
			vec.push_back(mp(pos,0));
			if(dfs(i+1,k-pos-len[i]))
			{
				if(!same(mp(pos,1),mp(pos+len[i],0),pos+len[i])) vec.push_back(mp(pos,1));else if(!ok[pos+len[i]]) vec.push_back(mp(pos+len[i],0));
			}
		}
		optimization=vec[0];
		for(int i=1;i<vec.size();i++)
		{
			if(compare(vec[i],optimization)) optimization=vec[i];
		}
		if(optimization.second==0) continue;
//		time=clock();
		sort(all(vec),compare);
//		size+=(int)vec.size();
//		SortUse+=clock()-time;
		memset(ok,0,sizeof(ok));
		for(int j=0;j<vec.size();j++)
		{
			if(j==0 || check(vec[0],vec[j]))
			{
				ok[vec[j].first+vec[j].second*len[var]]=true;
			}
		}
		cur.erase(cur.begin()+vec[0].first,cur.end());
		if(vec[0].second)
		{
			for(int j=0;j<len[i];j++)
			{
				cur.push_back(str[i][j]);
			}
		}
		for(int j=vec[0].first;j<vec[0].first+vec[0].second*len[i];j++)
		{
			curH[j]=(1LL*(j?curH[j-1]:0)*107+cur[j])%mod;
		}
//		init(cur,curH);
	}
	cout<<cur<<endl;
	return 0;
}