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>
using namespace std;
#define inf 0x3f3f3f3f
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ll long long
#define vi vector <int>
#define pii pair <int, int>
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i,n) for (int i = 0; i < (int) (n); ++ i)
#define foreach(it,c) for (__typeof(c.begin()) it = c.begin(); it != c.end(); ++ it)

inline int read() {
	int x = 0, f = 1, c = getchar();
	for (;!isdigit(c);c = getchar()) if (c == '-') f ^= 1;
	for (; isdigit(c);c = getchar()) x = x * 10 + c - '0';
	return f ? x : -x;
}

int n, K;
int tot;
char s[1000005];
int len[2005], ps[2005];
bool can[2005][10005];
bitset <1000005> seg[70], st;

char fnd() {
	int i = 1;
	while (i < 32) {
		if ((seg[i + i] & st).any()) i = i + i;
		else i = i + i + 1;
	}
	return 'a' + i - 32;
}

int main() {
	n = read(), K = read();
	rep(i, n) {
		scanf("%s", s + tot);
		len[i] = strlen(s + tot);
		tot += len[i], ps[i + 1] = tot;
	}
	can[n][0] = 1;
	for (int i = n - 1; ~i; -- i) rep(j, K + 1) if (can[i + 1][j]) {
		if (j + len[i] <= K) can[i][j + len[i]] = 1;
		can[i][j] = 1;
	}
	rep(i, 26) rep(j, tot) if (s[j] == i + 'a') seg[i + 32].set(j);
	for (int i = 31; i; -- i) seg[i] = seg[i + i] | seg[i + i + 1];
	st.set(0);
	rep(i, K) {
		rep(j, n) if (st.test(ps[j])) st.set(ps[j + 1]);
		rep(j, n) if (K - i - len[j] < 0 || !can[j + 1][K - i - len[j]]) st.reset(ps[j]);
//		rep(j, tot) if (st.test(j)) printf("%d ", j); puts("");
		char c = fnd(); putchar(c);
		st &= seg[c - 'a' + 32]; st <<= 1;
	}
	puts("");
	return 0;
}