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 <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

const int P1 = 1e9 + 103;
const int P2 = 1e9 + 289;
const int PV = 1e9 + 7;

pii PW[10010];
pii operator-(pii a, pii b) { return pii(a.Fi-b.Fi<0 ? a.Fi-b.Fi+P1 : a.Fi-b.Fi, a.Se-b.Se<0 ? a.Se-b.Se+P2 : a.Se-b.Se); }
pii operator+(pii a, pii b) { return pii(a.Fi+b.Fi>=P1 ? a.Fi+b.Fi-P1 : a.Fi+b.Fi, a.Se+b.Se>=P2 ? a.Se+b.Se-P2 : a.Se+b.Se); }
pii operator*(pii a, pii b) { return pii((ll)a.Fi*b.Fi%P1, (ll)a.Se*b.Se%P2); }

int N, K;
int dp[10010];
string s[2020];
char buf[100010];

char ans[10010];
pii sans[10010];
int dl;
int min_index[10010];

void write(int x, char c) {
	ans[x] = c;
	sans[x] = sans[x-1] + pii(c, c) * PW[x];
}

pii get_h1(int l, int r) {
	return (sans[r] - sans[l-1]) * PW[10005 - r];
}

vector <pii> In[2020];
pii get_h2(int x, int idx) {
	return In[x][idx] * PW[10005 - idx];
}

pair<string, int> X[2020];
int main() {
	PW[0] = pii(1, 1); for(int i=1;i<10010;i++) PW[i] = pii(PV, PV) * PW[i-1];
	scanf("%d%d", &N, &K);
	for(int i=1;i<=N;i++) {
		scanf("%s", buf);
		s[i] = (string)buf;
		X[i] = make_pair(s[i], i);
		pii now = pii(0, 0);
		for(int j=0;buf[j];j++) {
			now = now + pii(buf[j], buf[j]) * PW[j];
			In[i].pb(now);
		}
	}
	sort(X+1, X+1+N);
	
	for(int i=0;i<=K;i++) dp[i] = -1;
	dp[0] = N+1;
	for(int i=N;i;i--) {
		int x = szz(s[i]);
		for(int j=K;j>=x;j--) if(dp[j] == -1) {
			if(dp[j-x] != -1) dp[j] = i;
		}
	}
	for(int i=0;i<10010;i++) min_index[i] = N + 1, write(i, 'z' + 1);
	min_index[0] = 0;
	
	for(int L=0;L<=K;L++) {
		if(min_index[L] == N + 1) continue;
		int idx = min_index[L];
		for(int a=1;a<=N;a++) {
			int j = X[a].Se;
			if(j <= idx) continue;
			int lj = szz(X[a].Fi);
			if(L + lj > K || dp[K-L-lj] <= j) continue;
			
			int op = 0;
			int low = 0, high = lj - 1, fd = -1;
			while(low <= high) {
				int mid = (low + high) >> 1;
				if(get_h1(L+1, L+1+mid) != get_h2(j, mid)) fd = mid + 1, high = mid - 1;
				else low = mid + 1;
			}
			if(fd != -1) {
				op = (ans[L+fd] > X[a].Fi[fd-1]) ? 1 : -1;
			}
			if(op == -1) break;
			if(op == 0) {
				if(min_index[L+lj] > j) {
					min_index[L+lj] = j;
				}
			}
			else {
				for(int b=L+fd;b<=L+lj;b++) min_index[b] = N + 1, write(b, X[a].Fi[b-L-1]); // ans[b] = X[a].Fi[b-L-1];
				for(int b=L+lj+1;b<=K;b++) min_index[b] = N + 1, write(b, 'z'+ 1); // ans[b] = 'z' + 1;
				min_index[L+lj] = j;
			}
		}
	}
	for(int i=1;i<=K;i++) printf("%c", ans[i]); puts("");
	
	return 0;
}