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>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int reserved[20001];

int *buildZ(const string &s){
	int n = s.size();
	int *z = reserved;
	int l = 0, r = 0;
	
	memset(z, 0, sizeof(int)*(n + 1));
	for(int i = 1; i < n; i++){
		if(i <= r) z[i] = min(z[i - l], r - i + 1);
		while(i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
		if(i + z[i] - 1 > r){
			l = i;
			r = i + z[i] - 1;
		}
	}
	z[0] = n;
	return z;
}

int diff_point(const string &s, const string &t, int l1, int l2, int *z){
	if(l2 < l1) return diff_point(s, t, l2, l1, z);
	if(l1 < 0) return l2 < 0 ? s.size() : min((int)t.size(), z[t.size() + l2]) + l2;
	if(l1 == l2) return l1 + t.size();
	
	int l = z[t.size() + l1];
	if(l < l2 - l1) return l1 + min((int)t.size(), l);
	if(l2 - l1 >= t.size()) return l1 + t.size();
	l = l2 - l1;
	int m = z[l];
	return l1 + min(l + m, (int)t.size());
}
int compare(const string &s, const string &t, int l1, int l2, int *z){
	if(l1 == l2) return 0;
	if(l2 < l1) return -compare(s, t, l2, l1, z);
	int k = diff_point(s, t, l1, l2, z);
	if(l1 < 0){
		char c = k < s.size() ? s[k] : 0;
		char d = k < l2 ? s[k] : k - l2 < t.size() ? t[k - l2] : 0;
		if(c == d) return 0;
		return c < d ? -1 : 1;
	}
	
	char c = k < l1 ? s[k] : k - l1 < t.size() ? t[k - l1] : 0;
	char d = k < l2 ? s[k] : k - l2 < t.size() ? t[k - l2] : 0;
	if(c == d) return 0;
	return c < d ? -1 : 1;
}
bool prefix(const string &s, const string &t, int l1, int l2, int *z){
	if(l1 == l2) return 1;
	if(l2 < l1) swap(l1, l2);
	int k = diff_point(s, t, l1, l2, z);
	return k >= (l1 < 0 ? s.size() : l1 + t.size()) || k >= l2 + t.size();
}

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n, len; cin >> n >> len;
	vector<string> s(n);
	rep(i, n) cin >> s[i];
	
	vector<vector<bool>> go(n + 1, vector<bool>(len + 1));
	vector<vector<bool>> come(n + 1, vector<bool>(len + 1));
	go[n][len] = come[0][0] = 1;
	for(int i = n - 1; i >= 0; i--){
		go[i] = go[i + 1];
		for(int j = len; j >= s[i].size(); j--) if(go[i + 1][j]) go[i][j - s[i].size()] = 1;
	}
	
	string best = "";
	rep(i, n){
		int *z = buildZ(s[i] + best), next_l = -1;
		rep(j, len + 1) if(come[i][j] && j + s[i].size() <= len && go[i + 1][j + s[i].size()]){
			int k = compare(best, s[i], j, next_l, z);
			if(prefix(best, s[i], next_l, j, z) && (next_l < 0 ? best.size() : next_l + s[i].size()) < j + s[i].size()) next_l = j;
			else if(compare(best, s[i], j, next_l, z) < 0) next_l = j;
		}
		
		string next = next_l < 0 ? best : best.substr(0, next_l) + s[i];
		
		bool diff = 0;
		rep(j, len + 1){
			if(!diff && come[i][j]) come[i + 1][j] = 1;
			if(come[i][j] && j + s[i].size() <= len && go[i + 1][j + s[i].size()]){
				if(prefix(best, s[i], j, next_l, z)) come[i + 1][j + s[i].size()] = 1;
			}
			
			char c1 = j < best.size() ? best[j] : 0;
			char c2 = j < next.size() ? next[j] : 0;
			diff |= c1 != c2 || !c1 || !c2;
		}
		best = next;
	}
	cout << best << endl;
	
	return 0;
}