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<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
vector<int>zalgo(string s)
{
	vector<int>r;
	r.resize(s.size());
	r[0] = s.size();
	s.push_back('$');
	int pt = 1, kn = 0;
	for (;;)
	{
		if (pt == s.size() - 1)break;
		for (;;)
		{
			if (s[pt + kn] != s[kn])break;
			else kn++;
		}
		r[pt] = kn;
		int t = 1;
		for (;;)
		{
			if (r[t] < kn - t)r[pt + t] = r[t], t++;
			else break;
		}
		pt += t;
		kn = max(0, kn - t);
	}
	return r;
}
bool predp[2101][10101];
bool dp[2101][10101];
//string easy[100][100];
int main()
{
	int num, gen;
	scanf("%d%d", &num, &gen);
	vector<string>v;
	for (int i = 0; i < num; i++)
	{
		string s;
		cin >> s;
		v.push_back(s);
	}
	predp[num][gen] = true;
	for (int i = num - 1; i >= 0; i--)
	{
		for (int j = 0; j <= gen; j++)
		{
			if (predp[i + 1][j])
			{
				predp[i][j] = true;
				if (j >= v[i].size())predp[i][j - v[i].size()] = true;
			}
		}
		//for (int j = 0; j <= gen;j++)printf("%d ",predp[i][j]);
		//printf("\n");
	}
	string now;
	for (int i = 0; i < gen; i++)now.push_back('z' + 1);
	dp[0][0] = true;



	//for (int i = 0; i <= num; i++)for (int j = 0; j <= gen; j++)for (int k = 0; k <= gen; k++)easy[i][j].push_back('z' + 1);
	//easy[0][0] = "";
	
	
	
	for (int i = 0; i < num; i++)
	{
		//if (now.size() != gen)exit(0);
		/*for (int j = 0; j <= gen; j++)printf("%d ", dp[i][j]); printf("\n");
		cout << now << endl;


		for (int j = 0; j <= gen; j++)
		{
			easy[i + 1][j] = easy[i][j];
			if (j >= v[i].size())easy[i + 1][j] = min(easy[i + 1][j], easy[i][j - v[i].size()] + v[i]);
		}
		for (int j = 0; j <= gen; j++)
		{
			if (predp[i + 1][j])cout << easy[i + 1][j] << " ";
			else cout << "1" << " ";
		}
		printf("\n");*/

		



		string s = v[i];
		vector<int>dat = zalgo(s + "#" + now);
		int frm[10101];
		for (int j = 0; j <= gen; j++)
		{
			int t = 0;
			if (predp[i][j] && predp[i + 1][j] && dp[i][j])t++;
			if (j >= s.size() && predp[i][j - s.size()] && predp[i + 1][j] && dp[i][j - s.size()])t += 2;
			if (t == 0)frm[j] = -1;
			else if (t == 1)frm[j] = 0;
			else if (t == 2)frm[j] = 1;
			else
			{
				int x = dat[s.size() + 1 + (j - s.size())];
				if (x == s.size())frm[j] = 0;
				else if (now[j - s.size() + x] < s[x])frm[j] = 0;
				else frm[j] = 1;
			}
			//printf("%d ", frm[j]);
		}
		//printf("\n");
		int rr = -1;
		vector<int>ks;
		for (int j = gen; j >= 0; j--)
		{
			if (frm[j] == -1)continue;
			//cerr << j << " ";
			if (frm[j] == 0)
			{
				if (rr == -1)rr = j, ks.push_back(j);
				else if (frm[rr] == 0)ks.push_back(j);
				else
				{
					if (j <= rr - s.size())ks.push_back(j);
					else
					{
						int x = dat[s.size() + 1 + (rr - s.size())];
						if (x < j - (rr - s.size()))
						{
							if (now[rr - s.size() + x] < s[x])rr = j, ks.clear(), ks.push_back(j);
						}
						else ks.push_back(j);
					}
				}
			}
			else
			{
				if (rr == -1)rr = j, ks.push_back(j);
				else if (frm[rr] == 0)
				{
					int x = dat[s.size() + 1 + (j - s.size())];
					if (x < s.size())
					{
						if (s[x] < now[j - s.size() + x])rr = j, ks.clear(), ks.push_back(j);
					}
					else ks.push_back(j);
				}
				else
				{
					if (j <= rr - s.size())
					{
						int x = dat[s.size() + 1 + (j - s.size())];
						if (x < s.size())
						{
							if (s[x] < now[j - s.size() + x])rr = j, ks.clear(), ks.push_back(j);
						}
						else ks.push_back(j);
					}
					else
					{
						int x = dat[s.size() + 1 + (j - s.size())];
						if (x < rr - j)
						{
							if (s[x] < now[j - s.size() + x])rr = j, ks.clear(), ks.push_back(j);
						}
						else
						{
							int y = dat[rr - j];
							if (y < s.size() - (rr - j))
							{
								if (s[rr - j + y] < s[y])rr = j, ks.clear(), ks.push_back(j);
							}
							else ks.push_back(j);
						}
					}
				}
			}
		}
		//printf("--%d\n", rr);
		for (int j = 0; j < ks.size(); j++)dp[i + 1][ks[j]] = true;
		string nn;
		if (frm[rr] == 0)
		{
			for (int j = 0; j < rr; j++)nn.push_back(now[j]);
			for (int j = rr; j < gen; j++)nn.push_back('z' + 1);
		}
		else
		{
			for (int j = 0; j < rr - s.size(); j++)nn.push_back(now[j]);
			for (int j = 0; j < s.size(); j++)nn.push_back(s[j]);
			for (int j = rr; j < gen; j++)nn.push_back('z' + 1);
		}
		now = nn;
	}
	cout << now << endl;
}