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 endl '\n'

using namespace std;
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
const int MAXN = (1 << 11);
const int MAXK = (int)1e4 + 17;

int n, k;
string s[MAXN];

void read()
{
	cin >> n >> k;
	for(int i = 0; i < n; i++)
		cin >> s[i];
}

bitset<MAXK> dp[MAXN];
bitset<MAXK * 100> bs[26], curr, temp, pref_bs[26];
int last[MAXN];
vector<char> cli;

bool check(char let, int c_l)
{
	temp = (curr << 1) & pref_bs[let - 'a'];

	bool ok = 0;
	for(int i = 0; i < n; i++)
	{
		if(curr[last[i]]) ok = 1;
		if(ok && cli[last[i] + 1] <= let)
		{
			temp[last[i] + 1] = 0;
			if(c_l + (int)s[i].size() <= k && dp[i + 1][k - c_l - (int)s[i].size()]) 
				temp[last[i] + 1] = 1;
		}
	}

	return !temp.none();
}

void solve()
{
	dp[n][0] = 1;
	for(int i = n - 1; i >= 0; i--)
		dp[i] = dp[i + 1] | (dp[i + 1] << s[i].size());

	cli.push_back(0);
	for(int i = 0; i < n; i++)
	{
		for(char c: s[i])
			cli.push_back(c);

		last[i + 1] = cli.size() - 1;
	}

	for(int i = 1; i < (int)cli.size(); i++)
		bs[cli[i] - 'a'][i] = 1;

	for(int i = 0; i < 26; i++)
		pref_bs[i] = (i == 0) ? (bs[0]) : (pref_bs[i - 1] | bs[i]);

	string answer = "";
	curr[0] = 1;
	for(int c_l = 0; c_l < k; c_l++)
	{
		char let, low = 'a', high = 'z', mid;
		while(low <= high)
		{
			mid = (low + high) >> 1;

			if(check(mid, c_l))
				let = mid, high = mid - 1;
			else 
				low = mid + 1;
		}

		temp = (curr << 1) & bs[let - 'a'];

		bool ok = 0;
		for(int i = 0; i < n; i++)
		{
			if(curr[last[i]]) ok = 1;
			if(ok && cli[last[i] + 1] == let)
			{
				temp[last[i] + 1] = 0;
				if(c_l + (int)s[i].size() <= k && dp[i + 1][k - c_l - (int)s[i].size()]) 
					temp[last[i] + 1] = 1;
			}
		}

		answer += let;
		curr = temp;
	}

	cout << answer << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}