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;
const int N = 2e3+100;
const int K = 1e4+100;
typedef pair<int,int> pii;
#define fr(i,low,up,st) for(int i = low;i <= (int)up; i += st)
#define nfr(i,low,up,st) for(int i = low;i >= (int)up; i -= st)
#define SZ(a) (int)a.size()
#define fill(a,b) memset(a,b,sizeof a)
#define cpy(a,b) memcpy(a,b,sizeof a)
#define pb push_back

string str[N];
string a[N];
int isc[K];

string curs;
int z[K*2],exk[K*2];
vector<int> q1;

void z_algo(int stp,string s1){
   fill(z,0); fill(exk,0);
   z[1] = stp-1;
   int R = 0,mx = 0;
   fr(i,2,SZ(s1)-1,1){
      z[i] = (i < R)?min(R-i,z[i-mx+1]):0;
      while(i+z[i] < SZ(s1) && s1[z[i]+1] == s1[z[i]+i])++z[i];
      if(i+z[i] > R)R = i+z[i],mx = i;
   }
   fr(i,stp+1,SZ(s1)-1,1){
      exk[i-stp] = z[i];
   }
}

int f[N][K];
int n,k,cut[K*2];
bool flag;

int main(){
   scanf("%d%d",&n,&k);
   fr(i,1,n,1){
      cin >> str[i];
   }
   fill(f,0); f[n+1][k] = 1;
   nfr(i,n,1,1){
      nfr(j,k,0,1){
         f[i][j] |= f[i+1][j];
         if(j+SZ(str[i]) <= k)f[i][j] |= f[i+1][j+SZ(str[i])];
      }
   }

   cut[0] = 1;
   int curp;
   fr(i,1,n,1){
      q1.clear();
      string qry = " "+str[i]+" "+curs;
      int cz = SZ(curs);
      int sz = SZ(str[i]);
      z_algo(str[i].size()+1,qry);
      curp = -1; flag = false;
      nfr(j,k,0,1){
         if(j+sz > k || !cut[j] || !f[i+1][j+SZ(str[i])])continue ;
         if(curp == -1){
            if(exk[j+1] == sz)q1.pb(j+sz);
            else if(exk[j+1] == cz-j)q1.pb(j+sz),curp = j;
            else {
               if(str[i][exk[j+1]] < curs[j+exk[j+1]]){
                  q1.clear(); curp = j; flag = true;
               }
            }
         } else {
            if(exk[j+1] >= curp-j){
               if(z[curp-j+1] == (sz-curp+j))q1.pb(j+sz);
               else {
                  if(str[i][curp-j+z[curp-j+1]] < str[i][z[curp-j+1]]){
                     q1.clear(); curp = j; flag = true;
                  }
               }
            } else if(exk[j+1] == sz)q1.pb(j+sz);
            else {
               if(str[i][exk[j+1]] < curs[j+exk[j+1]]){
                  q1.clear(); curp = j; flag = true;
               }
            }
         }
      }

      if(curp > -1 && flag){
         fr(j,curp+1,k,1){
            if(j > curp+SZ(str[i]))cut[j] = 0;
            if(!cut[j])continue ;
            if(exk[curp+1] < j-curp)cut[j] = 0;
         }
      }
      fr(j,0,SZ(q1)-1,1)cut[q1[j]] = 1;
      q1.clear();
      if(curp > -1)curs = curs.substr(0,curp)+str[i];
      cut[SZ(curs)] = 1;
   }
   cout << curs << endl;
   return 0;
}