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;
using ll = long long;
using uint = unsigned int;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ~ ";
	dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif
vector<int> Zalgo(string s){
	int N = s.size();
	vector<int> Z(N);
	Z[0] = N;
	int i = 1, j = 0;
	while(i<N){
		while(i+j<N && s[j]==s[i+j]) ++j;
		Z[i] = j;
		if(j==0){
			++i;
			continue;
		}
		int k = 1;
		while(i+k<N && k+Z[k]<j) Z[i+k]=Z[k],++k;
		i += k, j -= k;
	}
	return Z;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);

	int N,X; cin >> N >> X;
	V<string> ss(N); rep(i,N) cin >> ss[i];
	VV<bool> can(N+1,V<bool>(X+1));
	can[0][0] = true;
	rep(i,N){
		int v = ss[N-1-i].size();
		rep(j,X+1) if(can[i][j]){
			can[i+1][j] = true;
			if(j+v <= X) can[i+1][j+v] = true;
		}
	
	}
	show(can);
	string pre;
	using P = pair<int,bool>;
	V<bool> isActive(X+1); isActive[0] = true;
	rep(t,N){
		V<P> nxt(X+1,P(-1,false));
		string s = ss[t];
		int n = si(s);
		V<int> Z = Zalgo(s+"$"+pre);
		auto getDif = [&](P x,P y){
			int a = x.fs, b = y.fs;
			if(!x.sc){
				if(a<=b) return a;
				int pfx = Z[n+1+b];
				return b+pfx;
			}else{
				if(!y.sc){
					return a+Z[n+1+a];
				}else{
					int pfx = Z[n+1+a];
					if(b-a <= n){
						if(pfx < b-a) return a+pfx;
						return b + Z[b-a];
					}else{
						return a + pfx;
					}
				}
			}
		};
		auto getChar = [&](P x,int i){
			if(i < x.fs) return pre[i];
			return s[i-x.fs];
		};
		auto Set = [&](P& x, P y){
			if(x.fs == -1){
				x = y;
				return;
			}
			int i = getDif(x,y);
			int sz = x.fs + (x.sc ? n : 0);
			if(i == sz) return;
			if(getChar(x,i) > getChar(y,i)) x = y;
		};
		rep(len,X+1) if(isActive[len]){
			Set(nxt[len],P(len,false));
			if(len+n <= X) Set(nxt[len+n],P(len,true));
		}
		stack<int> st;
		rep(len,X+1) if(can[N-1-t][X-len] && nxt[len].fs != -1){
			if(st.empty()){
				st.push(len);
				continue;
			}
			int prev = st.top();
			int i = getDif(nxt[prev],nxt[len]);
			show(len);show(prev);show(i);
			if(i == prev){
				st.push(len);
			}else if(getChar(nxt[prev],i) < getChar(nxt[len],i)){
			}else{
				while(!st.empty() && st.top() > i) st.pop();
				st.push(len);
			}
		}
		int mx = st.top();
		rep(i,X+1) isActive[i] = false;
		while(!st.empty()){
			isActive[st.top()] = true;
			st.pop();
		}
		if(!nxt[mx].sc) pre = pre.substr(0,mx);
		else pre = pre.substr(0,nxt[mx].fs)+s;

		shows("--------- t done = ",t);
		show(mx);
		show(pre);
		show(nxt);
		show(isActive);

		assert(si(pre) == mx);
	}
	cout << pre << endl;
}