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;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

vector<int> Z_algo(const string &S) {
	vector<int> A(S.size());
	A[0] = S.size();
	int i = 1, j = 0;
	while (i < S.size()) {
		while (i+j < S.size() && S[j] == S[i+j]) ++j;
		A[i] = j;
		if (j == 0) { ++i; continue; }
		int k = 1;
		while (i+k < S.size() && k+A[k] < j) A[i+k] = A[k], ++k;
		i += k; j -= k;
	}
	return A;
}

const int MN = 2010;
const int MK = 10010;

bool can[MN][MK], dp[MN][MK];

void update(string &s, string t) {
	int ml = min(s.size(), t.size());

	rep(i, ml) {
		if (s[i] > t[i]) {
			s = t;
			return ;
		}
		if (s[i] < t[i]) {
			return ;
		}
	}
	if (ml < t.size()) {
		s = t;
	}
}

int main() {
	//test
	int N, K; cin >> N >> K;
	vector<string> s(N), com(N+1);
	rep(i, N) cin >> s[i];

	can[N][K] = true;
	for (int i = N-1; i >= 0; --i) {
		for (int j = 0; j <= K; ++j) {
			can[i][j] = can[i + 1][j];
			if (j + s[i].size() <= K) {
				can[i][j] |= can[i + 1][j + s[i].size()];
			}
		}
	}

	dp[0][0] = true;

	rep(i, N) {
		int sl = s[i].size();
		string cand = s[i] + com[i];
		vi zv = Z_algo(cand);

		bool same = false;
		vi pos;

		for (int j = 0; j <= com[i].size(); ++j) if (dp[i][j]) {
			if (can[i+1][j]) {
				same = true;
			}
			if (j + sl <= K && can[i + 1][j + sl]) {
				pos.pb(j);
			}
		}
		reverse(ALL(pos));

		int tp = 0;
		int piv = -1;

		if (pos.size() == 0) {
			tp = 1;
		} else {
			piv = pos[0];

			for (int pp = 1; pp < pos.size(); ++pp) {
				int p = pos[pp];
				int cl = zv[p + sl];

				if (piv - p >= sl) {
					if (cl < sl) {
						if (com[i][p + cl] > s[i][cl]) {
							piv = p;
						}
					}
				} else {
					if (cl < piv - p) {
						if (com[i][p + cl] > s[i][cl]) {
							piv = p;
						}
					} else {
						cl -= piv - p;
						cl = zv[cl];
						if (cl < sl - (piv - p)) {
							if (s[i][cl] > s[i][piv-piv+cl]) {
								piv = p;
							}
						}
					}
				}
			}

			if (same) {
				int cl = zv[piv + sl];		
				if (piv + sl <= com[i].size()) {						
					if (cl >= sl) {
						tp = 1;
					} else {
						if (com[i][piv + cl] < s[i][cl]) {
							tp = 1;
						}
					}
				} else {
					if (piv + cl < com[i].size()) {
						if (com[i][piv + cl] < s[i][cl]) {
							tp = 1;
						}
					}
				}
			}
		}

		if (tp) {
			com[i + 1] = com[i];
			for (int j = 0; j <= com[i].size(); ++j) {
				dp[i + 1][j] = dp[i][j];
			}
		} else {
			com[i + 1] = com[i].substr(0, piv) + s[i];
			bool same_pref = true;
			string cmp = s[i] + com[i + 1];
			vi vcmp = Z_algo(cmp);

			for (int j = 0; j <= com[i].size(); ++j) {
				if (dp[i][j] && can[i+1][j] && same_pref) {
					dp[i+1][j] = true;
				}
				if (j + s[i].size() <= K && dp[i][j] && can[i+1][j+s[i].size()] && com[i+1].size() >= j + s[i].size() && same_pref && vcmp[j + sl] >= sl) {
					dp[i+1][j+s[i].size()] = true;
				}
				if (com[i+1].size() <= j || com[i][j] != com[i+1][j]) {
					same_pref = false;
				}
			}
		}
	}

	cout << com[N] << endl;

	return 0;
}