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:
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

const int INF=5e8;

namespace SAIS{
  static const int MAX_N=1000005;
  typedef vector<int> vi;
  typedef vector<bool> vb;
  int bkt[MAX_N+1];
  void setBuckets(int* s, int n, int K,bool end){
    for(int i=0;i<=K;++i) bkt[i]=0;
    for(int i=0;i<n;++i) bkt[s[i]]++;
    int sum=0;
    for(int i=0;i<=K;++i){
      sum+=bkt[i];
      bkt[i]=(end?sum:sum-bkt[i]);
    }
  }
  void induceSAL(const vb& t,int* SA,int* s,int n,int K,bool end){
    setBuckets(s,n,K,end);
    int j;
    for(int i=0;i<n;++i){
      j=SA[i]-1;
      if(j>=0 && !t[j]) SA[bkt[s[j]]++]=j;
    }
  }
  void induceSAS(const vb& t,int* SA,int* s,int n,int K,bool end){
    setBuckets(s,n,K,end);
    int j;
    for(int i=n-1;i>=0;--i){
      j=SA[i]-1;
      if(j>=0 && t[j]) SA[--bkt[s[j]]]=j;
    }
  }
#define isLMS(i) (i>0 && t[i] && !t[i-1])
  void SA_IS(int* s,int *SA,int n,int K){
  //s[n-1] is assumed to be 0
  //each element of s[0...n-2] \in [1...K]
    vector<bool> t(n);

    t[n-1]=1;//1 for S
    t[n-2]=0;//0 for L
    for(int i=n-3;i>=0;--i){
      if(s[i]<s[i+1] || (s[i]==s[i+1] && t[i+1]==1)) t[i]=1;
      else t[i]=0;
    }
    setBuckets(s,n,K,true);
    for(int i=0;i<n;++i) SA[i]=-1;
    for(int i=1;i<n;++i) if(isLMS(i)) SA[--bkt[s[i]]]=i;

    induceSAL(t,SA,s,n,K,false);
    induceSAS(t,SA,s,n,K,true);

    int n1=0;
    for(int i=0;i<n;++i) if(isLMS(SA[i])) SA[n1++]=SA[i];

    for(int i=n1;i<n;++i) SA[i]=-1;
    int rank=0, prev=-1;
    for(int i=0;i<n1;++i){
      int pos=SA[i];
      bool dif=false;
      for(int d=0;d<n;++d){
        if(prev==-1 || s[pos+d]!=s[prev+d] || t[pos+d]!=t[prev+d]){
          dif=true;
          break;
        }else if(d>0 && (isLMS(pos+d) || isLMS(prev+d))) break;
      }
      if(dif){
        ++rank;
        prev=pos;
      }
      pos>>=1;
      SA[n1+pos]=rank-1;
    }
    for(int i=n-1,j=n-1;i>=n1;--i) if(SA[i]>=0) SA[j--]=SA[i];

    int *SA1=SA,*s1=SA+n-n1;
    if(rank<n1) SA_IS(s1,SA1,n1,rank-1);
    else for(int i=0;i<n1;++i) SA1[s1[i]]=i;


    setBuckets(s,n,K,true);
    for(int i=1,j=0;i<n;++i) if(isLMS(i)) s1[j++]=i;
    for(int i=0;i<n1;++i) SA1[i]=s1[SA1[i]];
    for(int i=n1;i<n;++i) SA[i]=-1;
    for(int i=n1-1,j;i>=0;--i){
      j=SA[i];
      SA[i]=-1;
      SA[--bkt[s[j]]]=j;
    }
    induceSAL(t,SA,s,n,K,false);
    induceSAS(t,SA,s,n,K,true);
  }
  int tmp[MAX_N];
  void SA_IS(char* s,int* SA,int n){
    REP(i,n) tmp[i]=s[i];
    SA_IS(tmp,SA,n,260);
  }
  void buildLCP(char* s,int* sa,int* rev,int* lcp,int n){
    int h=0;
    REP(i,n) rev[sa[i]]=i;
    REP(i,n-1){
      if(rev[i]==n-1) lcp[rev[i]]=0;
      else{
        for(int j=sa[rev[i]+1];j+h<n && i+h<n && s[i+h]==s[j+h];++h);
        lcp[rev[i]]=h;
      }
      if(h>0) --h;
    }
  }
};

int n,k;
string s[2005];

char cur[10005];
int sa[10005],rev[10005],lcp[10005];
bool able[10005];

bool lower(const string& s,char* t){
  int len=min((int)s.size(),(int)strlen(t));
  REP(i,len) if(s[i]!=t[i]){
    return s[i]<t[i];
  }
  return false;
}
bool lower2(const string& s,char* t){
  int len=min((int)s.size(),(int)strlen(t));
  REP(i,len){
    if(s[i]!=t[i]){
      return s[i]<t[i];
    }
  }
  return (int)s.size()<(int)strlen(t);
}
int common(const string& s,char* t){
  int len=min((int)s.size(),(int)strlen(t));
  REP(i,len) if(s[i]!=t[i]) return i;
  return len;
}

bool dp[2005][10005];

char t[1000005];

int sa2[1000005],rev2[1000005],lcp2[1000005];
int main(){
  cin>>n>>k;
  REP(i,n) cin>>s[i];

  dp[n][k]=1;
  for(int i=n;i>0;--i) REP(j,k+1) if(dp[i][j]){
    dp[i-1][j]=true;
    if(j>=s[i-1].size()) dp[i-1][j-s[i-1].size()]=true;
  }

  int m=2;
  cur[0]='z'+1;
  cur[1]='\0';
  able[0]=1;
  REP(i,n){
    strcpy(t,s[i].c_str());
    int len=s[i].size();
    t[len]='z'+1;
    ++len;
    t[len]=0;
    SAIS::SA_IS(cur,sa,m);
    SAIS::buildLCP(cur,sa,rev,lcp,m);

    SAIS::SA_IS(t,sa2,len+1);
    SAIS::buildLCP(t,sa2,rev2,lcp2,len+1);

    int lb=-1,ub=m;
    while(ub-lb>1){
      int md=(lb+ub)>>1;
      if(lower(s[i],cur+sa[md])) ub=md;
      else lb=md;
    }

    int L=common(s[i],cur+sa[ub]);

    int minpos=INF,start=-1;
    int L2;
    for(int j=ub;j<m;++j){
      if(j!=ub) chmin(L,lcp[j-1]);
      if(L<s[i].size() && sa[j]+L<k && minpos>=sa[j]+L && able[sa[j]] && sa[j]+s[i].size()<=k && dp[i+1][sa[j]+s[i].size()]){
        if(minpos>sa[j]+L){
          minpos=sa[j]+L;
          start=sa[j];
          L2=L;
        }else{
          int p=minpos-start;
          int q=L;
          if(rev2[p]>rev2[q]){
            L2=q;
            start=sa[j];
          }
        }
      }
    }
    if(minpos<INF){
      REPN(j,m+1,minpos+1) able[j]=0;
      int j;
      for(j=0;j<s[i].size() && start+j<k;++j) cur[start+j]=s[i][j];
      j+=start;
      cur[j++]='z'+1;
      cur[j++]='\0';
      m=j;
    }
    {
      SAIS::SA_IS(cur,sa,m);
      SAIS::buildLCP(cur,sa,rev,lcp,m);
      int lb=-1,ub=m;
      while(ub-lb>1){
        int md=(lb+ub)>>1;
        if(lower2(s[i],cur+sa[md])) ub=md;
        else lb=md;
      }
      int L=common(s[i],cur+sa[ub]);
      for(int j=ub;j<m;++j){
        if(j!=ub) chmin(L,lcp[j-1]);
        if(L<s[i].size()) break;
        if(able[sa[j]] && sa[j]+s[i].size()<=k && dp[i+1][sa[j]+s[i].size()])
          able[sa[j]+s[i].size()]=1;
      }
    }
  }

  assert(m==k+2);
  cur[k]=0;
  printf("%s\n",cur);
  return 0;
}