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:
/*----------------by syr----------------*/
/*

         iii                  ii
     rBQBBBBBBE       BBR iBBBBQBBL     XBBBBBBQBBBBB
   iBBQJ    7BBB      BBsSBBr   BBQ      i      cBBB
  rBBU       iBBw     BBBQi     HBBi           KBBi
  BBH         BB5    iBBB       isL          wBB5
 GBB         iBBi    6BB                   iBBB
 BBQ         BQB     BBD                  QBBi
 BBB        BQB     iQBi                1BBv
 sBBg     wBBB      QBB               iBBB
  7BBBBBBBBBi       BBR              wBBBBBBBBBBBBB
     irvi           ii               ii    i i iii
                i5U
               BBB
               BB7
              1BB
      iPBBBBBKBBR    JBR1       rQBO   BR  UBQP  iBBQi
    7BBBGs7sXBBBi     QBBr     gBBE   rBB BB2BB7HBZQBB
   QBBi      sBQ       BBB   iBBB     SQBBR  BBBB  cBQ
  gBQ        BBg        BBB KBBi      MBBH   BBB   BBs
 iBBv       iBBi         QBBBL        BBR   pBB   iBB
 pBB        BBB         iBBBB        iBB    BBL   KBB
 MBB       BBBR        BBB JBBi      DBR   iBQ    BBL
 GBB     7BBBB2      PBBH   BBBi     BQr   DBB   iBB
  BQBXwgBBP BB7    1BBB      BBQ7   1BB    BBc   BBB
   2BBBBw   BB    EBBS        QBBi  HBa   iBB    BB7
*/
#include<bits/stdc++.h>

using namespace std;

#define PH push
#define MP make_pair
#define PB push_back
#define fst first
#define snd second
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define x0 x0123456789
#define y0 y0123456789
#define x1 x1234567890
#define y1 y1234567890
#define x2 x2345678901
#define y2 y2345678901
typedef double db;
typedef long long ll;
typedef long double ldb;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 7;
const int maxn = 2005;
const int maxm = 1e6 + 5;
const int maxk = 1e4 + 5;
const int sigma = 65;

int n, k, tot = 0;
int beg[maxn], l[maxn];
int dp[maxn][maxk];
char str[maxm], ans[maxk];
char s[maxn][maxk];
bitset<maxm> segt[sigma];

int query(bitset<maxm> cur){
	int u;
	for(u = 1; u < 32; ){
		if(!(cur & segt[u << 1]).none()) u <<= 1;
		else (u <<= 1) += 1;
	}
	return u - 32;
}

int main(){
	scanf("%d%d", &n, &k);
	FOR(i, 0, n){
		scanf("%s", s[i]);
		l[i] = strlen(s[i]);
	}
	dp[n][0] = 1;
	for(int i = n - 1; i >= 0; --i) FOR(j, 0, k){
		dp[i][j] |= dp[i + 1][j];
		if(l[i] <= j) dp[i][j] |= dp[i + 1][j - l[i]];
	}
	//puts("ok");
	FOR(i, 0, n){
		beg[i] = tot;
		FOR(j, 0, l[i]){
			segt[s[i][j] - 'a' + 32].set(tot);
			str[tot++] = s[i][j];
		}
		//printf("%d\n", beg[i]);
	}
	beg[n] = tot;
	for(int i = 31; i; --i) segt[i] = segt[i << 1] | segt[i << 1 | 1];
	bitset<maxm> cur;
	cur.set(0);
	//puts("ok");
	FOR(i, 0, k){
		FOR(j, 0, n) if(cur[beg[j]]) cur.set(beg[j + 1]);
		FOR(j, 0, n) if(l[j] > k - i || !dp[j + 1][k - i - l[j]]) cur.reset(beg[j]);
		int nxt = query(cur);
		//printf("nxt = %d\n", nxt);
		cur &= segt[nxt + 32];
		cur <<= 1;
		ans[i] = nxt + 'a';
	}
	puts(ans);
	return 0;
}