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 <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

#ifndef LOCAL
#define cerr _cer
struct _cert
{
    template <typename T> _cert& operator << (T) { return *this; }
};
_cert _cer;
#endif

template <typename T> void dprint(T begin, T end) {
    for (auto i = begin; i != end; i++) {
		cerr << (*i) << " ";
    }
    cerr << "\n";
}
const int MX = 1200000;

int z[MX];
string s[2100];
string t;
string bs;
int av[MX];

void calcz() {
	z[0] = 0;
	int l = 0, r = 0;
	for (int i = 1; i < t.size(); ++i) {
		if (r > i)
			z[i] = min(r - i, z[i - l]);
		else
			z[i] = 0;
		while (i + z[i] < t.size() && t[z[i]] == t[i + z[i]])
			++z[i];
		if (i + z[i] > r)
			r = i + z[i], l = i;
	}
	z[t.size()] = 0;
}

int n, k;
char buf[MX];
int dp[2100][11000];

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; ++i) {
		scanf(" %s", buf);
		s[i] = buf;
	}
	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];
		for (int j = 0; j + s[i].size() <= k; ++j)
			dp[i][j + s[i].size()] |= dp[i + 1][j];
	}
	av[0] = 1;
	for (int i = 0; i < n; ++i) {
		int bstp = -1;
		pair<int, char> bst = make_pair(k + 1, 0);
		t = s[i] + "$" + bs;
		calcz();
		int len = s[i].size();
		for (int j = 0; j <= bs.size(); ++j) {
			if (av[j] && (j + len <= k) && dp[i + 1][k - j - len]) {
				int cm = z[len + 1 + j];
				if (cm < len && j + cm < bs.size() && s[i][cm] < bs[j + cm]) {
					if (make_pair(j + cm, s[i][cm]) < bst)
						bst = make_pair(j + cm, s[i][cm]), bstp = j;
				}
			}
		}
		if (bstp != -1) {
			for (int i = bst.first + 1; i <= bs.size(); ++i)
				av[i] = 0;
			bs.resize(bstp);
			bs += s[i];
			av[bs.size()] = 1;
		}
		else {
			int lst = -1;
			for (int j = 0; j <= bs.size(); ++j) {
				if (av[j] && (j + len) <= k && dp[i + 1][k - j - len]) {
					int cm = z[len + 1 + j];
					if (j + cm == bs.size()) {
						if (lst == -1)
							lst = j;
						else {
							int cm = z[j - lst];
							if (j - lst + cm == s[i].size() || s[i][cm] < s[i][j - lst +cm])
								lst = j;
						}
					}
				}
			}
			if (lst != -1) {
				bs.resize(lst);
				bs += s[i];
				av[bs.size()] = 1;
			}
		}
		t = s[i] + "$" + bs;
		calcz();
		for (int j = (int)bs.size() - 1; j >= 0; --j) {
			if (av[j] && (j + len <= k) && dp[i + 1][k - j - len]) {
				int cm = z[len + 1 + j];
				if (cm == len) {
					av[j + len] = 1;
				}
			}
		}
	}
	cout << bs << "\n";
	return 0;
}