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;

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

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

pair<string, int> X[2020];
int main() {
	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);
	}
	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, ans[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 fd = -1, op = 0;
			for(int k=0;k<lj;k++) {
				if(ans[L+k+1] != X[a].Fi[k]) {
					if(ans[L+k+1] > X[a].Fi[k]) op = 1;
					else op = -1;
					fd = k + 1;
					break;
				}
			}
			
			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, ans[b] = X[a].Fi[b-L-1];
				for(int b=L+lj+1;b<=K;b++) min_index[b] = N + 1, ans[b] = 'z' + 1;
				min_index[L+lj] = j;
			}
		}
	}
	for(int i=1;i<=K;i++) printf("%c", ans[i]); puts("");
	
	return 0;
}