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;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 2005;
const int MAXK = 10005;

int n, k;
string s[MAXN];
bool dp2[MAXN][MAXK];
bool opt[MAXN][MAXK]; // which prefix of opts[i] is optimal at this moment?
string opts[MAXN];
char buf[MAXK];

int main(){
	scanf("%d %d",&n,&k);
	for(int i=1; i<=n; i++){
		scanf("%s", buf);
		s[i] = buf;
	}
	dp2[n+1][k] = 1;
	for(int i=n; i; i--){
		memcpy(dp2[i], dp2[i+1], sizeof(dp2[i]));
		for(int j=0; j+s[i].size()<=k; j++){
			dp2[i][j] |= dp2[i+1][j+s[i].size()];
		}
	}
	opt[0][0] = 1;
	for(int i=1; i<=n; i++){
		vector<int> vect(k + 1);
		for(int j=0; j<=k; j++){
			int transitable = 0;
			if(dp2[i+1][j] && opt[i-1][j]) transitable |= 1;
			if(dp2[i+1][j] && j >= s[i].size() && opt[i-1][j - s[i].size()]) transitable |= 2;
			if(transitable == 3){
				if(opts[i-1].substr(j - s[i].size(), s[i].size()) <= s[i]) transitable = 1;
				else transitable = 2;
			}
			vect[j] = transitable;
		}
		int lst = 0;
		for(int j=0; j<=k; j++){
			if(vect[j] == 1){
				lst = j;
			}
		}
		string cnd1 = opts[i-1].substr(0, lst);
		string cnd2 ="";
		for(int j=k; j>=s[i].size(); j--){
			if(vect[j] == 2){
				string this_part = opts[i-1].substr(0, j - s[i].size()) + s[i];
				if(cnd2.empty() || cnd2.substr(0, this_part.size()) > this_part){
					cnd2 = this_part;
				}
			}
		}
		if(cnd1.size() > cnd2.size()) swap(cnd1, cnd2);
		opts[i] = min(cnd1, cnd2);
		if(cnd2.substr(0, cnd1.size()) == cnd1) opts[i] = cnd2;

		vector<int> fail(s[i].size() + 1);
		vector<int> mtch(opts[i].size() + 1);
		int p = 0;
		for(int j=1; j<s[i].size(); j++){
			if(p && s[i][j] != s[i][p]) p = fail[p];
			if(s[i][j] == s[i][p]) p++;
			fail[j + 1] = p;
		}
		p = 0;
		for(int j=0; j<opts[i].size(); j++){
			while(p && opts[i][j] != s[i][p]) p = fail[p];
			if(opts[i][j] == s[i][p]) p++;
			if(s[i].size() == p){
				mtch[j + 1] = 1;
				p = fail[p];
			}
		}

		int lcp = 0;
		while(lcp < opts[i].size() && lcp < opts[i-1].size() && opts[i][lcp] == opts[i-1][lcp]) lcp++;
		for(int j=0; j<=lcp; j++){
			if(vect[j] == 1) opt[i][j] = 1;
			if(j + s[i].size() <= opts[i].size() && vect[j + s[i].size()] == 2 && mtch[j + s[i].size()]){
				opt[i][j + s[i].size()] = 1;
			}
		}
	}
	puts(opts[n].c_str());
}