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>
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)
#define N 2005
#define M 10005
#define ll long long
using namespace std;
int n, m, len, tp, tot, a[N], q[M], f[M<<1];
char s[N][M], s1[M<<1], ch[M];
bool fl[N][M], ok[M], vis[M];
struct node {
	int x, y; node() {}//x,y表示，将ch中的长为x的串和a[i]拼起来
	node(int a, int b) { x = a, y = b; }
} b[M];
inline void exkmp(char s[], int n) {
	int k = 1; memset(f, 0, sizeof f); f[1] = n;
	rep(i, 2, n) {
		f[i] = max(0, min(k+f[k]-i, f[i-k+1]));
		while(i+f[i] <= n && s[f[i]+i] == s[f[i]+1]) f[i]++;
		if(k == 1 || f[i]+i > f[k]+k) k = i;
	}
}
inline int cmp(const node &u, const node &v) {//比较函数，-1/0/1表示</=/>，等于相当于存在真包含关系
	if(!u.y && !v.y) return 0;
	if(!u.y) return -cmp(v, u);
	if(!v.y) {
		if(v.x < u.x) return 0;
		int t = f[u.x+u.y+1];
		if(u.x+t >= v.x) return 0;
		return s1[t+1] < s1[u.x+u.y+t+1] ? -1 : 1;
	}
	if(u.x == v.x) return 0;
	if(u.x > v.x) return -cmp(v, u);
	int t = f[u.x+u.y+1];
	if(u.x+t <= v.x) return s1[t+1] < s1[u.x+u.y+t+1] ? -1 : 1;
	t = f[v.x-u.x+1];
	if(v.x+t >= u.x) return 0;
	return s1[v.x-u.x+t+1] < s1[t+1] ? -1 : 1;
}
bool operator < (const node &x, const node &y) { return cmp(x, y) < 0; }
bool operator == (const node &x, const node &y) { return !cmp(x, y); }
int main() {
	scanf("%d%d", &n, &m);//a[i]是第i个串的长度
	rep(i, 1, n) { scanf("%s", s[i]+1); a[i] = strlen(s[i]+1); }
	fl[n+1][0] = 1;//fl[i][j]表示i到n的串中是否能拼出长度为j的串
	per(i, n, 1) rep(j, 0, m) {
		fl[i][j] = fl[i+1][j];//不选第i个串
		if(j >= a[i]) fl[i][j] |= fl[i+1][j-a[i]];//选第i个串
	}
	//ch保存目前为止【不考虑长度的字典序最小】且【最长】的串，并且之后是能拼出长度m的串的
	//ok[i]=1表示这是一个断点，len保存长度
	len = 0; ok[0] = 1;
	rep(i, 1, n) {
		if(!len) {
			if(fl[i+1][m-a[i]]) rep(j, 1, a[i]) ch[++len] = s[i][j];
			ok[len] = 1; continue;
		}
		//将当前串s[i]和目前最优串ch拼起来，exkmp预处理出任意一个后缀与该串的lcp，用f保存
		tot = 0;
		rep(j, 1, a[i]) s1[++tot] = s[i][j];//s1保存拼接后的串
		rep(j, 1, len) s1[++tot] = ch[j];
		exkmp(s1, tot);
		memset(vis, 0, sizeof vis);
		rep(j, 0, m) if(fl[i+1][m-j]) {//枚举前i个串能拼成的合法长度
			if(ok[j]) { vis[j] = 1; b[j] = node(j, 0); }
			if(j >= a[i] && ok[j-a[i]]) {
				if(vis[j]) b[j] = min(b[j], node(j-a[i], a[i]));
				else { vis[j] = 1; b[j] = node(j-a[i], a[i]); }
			}
		}
		q[1] = 0; tp = 1;
		rep(j, 1, m) if(vis[j]) {
			while(tp > 1 && b[j] < b[q[tp]]) tp--;
			if(b[j] == b[q[tp]]) q[++tp] = j;
		}//这里的'=='表示是一个真包含关系，都要保存下来，记录断点
		len = q[tp];
		if(b[len].y) rep(j, 1, a[i]) ch[b[len].x+j] = s[i][j];
		ch[len+1] = 0;
		memset(ok, 0, sizeof ok);
		while(tp) ok[q[tp--]] = 1;
	}//由于每次操作都保证了之后的串能拼出长度为m的，所以最后的答案长一定为m
	printf("%s\n", ch+1);
	return 0;
}