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:
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int N = 2010;
const int M = 10100;
typedef long long ll;
const int mod = 998244353;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
int n, k;
char s[N][M];
int len[N];
int hs[M], pw[M];
const int base = 233;
 
char ans[M][M];
bool has[M];
inline int cmp(char * s0, char * s1, int len) {
	for(int i = 0;i < len;++i, ++ s0, ++ s1) if(*s0 != *s1) return *s0 < *s1 ? 1 : -1;
	return 0;
}
int ok[N][M];
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	ok[0][0] = 1;
	*pw = 1;
	for(int i = 1;i < M;++i) pw[i] = (ll) pw[i - 1] * base % mod;
	rep(i, 1, n) {
		cin >> s[i];
		len[i] = strlen(s[i]);
		rep(j, 0, k) {
			ok[i][j] = ok[i - 1][j] || j >= len[i] && ok[i - 1][j - len[i]];
		}
	}
	has[0] = 1;
	for(int i = n;i >= 1;--i) {
		int val = 0;
		for(int j = 0;j < len[i];++j) val = (val + (ll) s[i][j] * pw[j]) % mod;
		for(int j = k;j >= len[i];--j) if(ok[i - 1][k - j]) {
			if(has[j - len[i]]) {
				int o = ((ll) hs[j - len[i]] * pw[len[i]] + val) % mod;
				int flag = 0;
				if(!has[j]) {
					flag = 1;
				} else if(o != hs[j]) {
					int c = cmp(ans[j], s[i], len[i]);
					if(c <= 0) flag = c || cmp(ans[j] + len[i], ans[j - len[i]], j - len[i]) == -1;
				}
				if(flag) {
					hs[j] = o;
					has[j] = 1;
					memcpy(ans[j], s[i], len[i]);
					memcpy(ans[j] + len[i], ans[j - len[i]], j - len[i]);
				}
			}
		}
	}
	cout << ans[k] << '\n';
}