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;

char s[2010][10010];
int len[2010];
int sum[2010];
char ss[1000010];
int tot;
bitset <1000010> pos;
bitset <1000010> node[70];
bool dp[2010][10010];

void get_pre(){
	for (int i = 0; i < tot; i++){
		node[ss[i] - 'a' + 32].set(i);
	}
	for (int i = 31; i >= 1; i--){
		node[i] = node[i << 1] | node[i << 1 | 1];
	}
}

char get_min(){
	int now = 1;
	while (now < 32){
		if ((pos & node[now << 1]).none()) now = now << 1 | 1;
		else now = now << 1;
	}
	return (now - 32) + 'a';
}

int main(){
	int n, k; scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++){
		scanf("%s", s[i]), len[i] = strlen(s[i]);
		sum[i] = tot;
		for (int j = tot; j < tot + len[i]; j++){
			ss[j] = s[i][j - tot];
		}
		tot += len[i];
	}
	sum[n] = tot;
	dp[n][0] = 1;
	for (int i = n - 1; i >= 0; i--){
		for (int j = 0; j <= k; j++){
			dp[i][j] = dp[i + 1][j];
			if (j >= len[i]) dp[i][j] |= dp[i + 1][j - len[i]];
		}
	}
	get_pre();
	pos.reset(), pos.set(0);
	string ans;
	for (int i = 0; i < k; i++){
		for (int j = 0; j < n; j++){
			if (pos[sum[j]]) pos.set(sum[j + 1]);
		}
		for (int j = 0; j < n; j++){
			if (k - i - len[j] < 0 || !dp[j + 1][k - i - len[j]]) pos.reset(sum[j]);
		}
		char c = get_min();
		ans.push_back(c);
		pos &= node[32 + c - 'a'];
		pos <<= 1;
	}
	printf("%s\n", ans.c_str());
	return 0;
}