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 ll long long
#define FIO "agc58F"
using namespace std;

const int N=2e3+5,K=1e4+5,S=1e6+5;

bitset<K>f[N];

int n,len[N],k,l;
char s[N][K],ans[K];

namespace Z{
  int ext[K],nxt[K];
  int n,m;
  char s[K],t[K];

  inline void build(char ss[K],char tt[K],int nn,int mm){
    n=nn;m=mm;
    for(int i=0;i<n;i++)s[i]=ss[i];
    for(int i=0;i<m;i++)t[i]=tt[i];
    int mid=0;
    nxt[0]=0;
    for(int i=1;i<n;i++){
      if(nxt[mid]+mid>=i+nxt[i-mid])nxt[i]=nxt[i-mid];
      else nxt[i]=max(0,mid+nxt[mid]-i);
      while(i+nxt[i]<n&&s[nxt[i]]==s[i+nxt[i]])nxt[i]++;
      if(i+nxt[i]>mid+nxt[mid])mid=i;
    }

    mid=0;
    ext[0]=0;
    //!!! ext<= min(n,m)
    while(t[ext[0]]==s[ext[0]]&&ext[0]<min(n,m))ext[0]++;
    for(int i=1;i<m;i++){
      if(ext[mid]+mid>=i+nxt[i-mid])ext[i]=nxt[i-mid];
      else ext[i]=max(0,mid+ext[mid]-i);
      while(ext[i]<n&&i+ext[i]<m&&s[ext[i]]==t[i+ext[i]])ext[i]++;
      if(i+ext[i]>mid+ext[mid])mid=i;
    }
    nxt[0]=n;


    /*
       puts("_______");
       for(int i=0;i<n;i++)putchar(s[i]);puts("");
       for(int i=0;i<m;i++)putchar(t[i]);puts("");
       for(int i=0;i<n;i++)printf("%d%c",nxt[i],i^n-1?' ':'\n');
       for(int i=0;i<m;i++)printf("%d%c",ext[i],i^m-1?' ':'\n');
       puts("______");
       */

    //ext[i] = lcp (ans[i],cur)

  }

  inline int cmp(int pos){
    int d=ext[pos];
    if(pos+d>=min(n,m))return 0;
    return s[pos+d]<t[d]?-1:1;
  }

}

#define pii pair<int,bool>
#define xx first
#define yy second

bitset<K> ok,vis;

pii a[K];

int st[K],t;

inline int cmpc(char a,char b){return a<b?-1:1;}

inline int cmp(pii x,pii y){
  if(0)printf("cmping %d,%d:%d,%d\n",x.xx,x.yy,y.xx,y.yy);
  if(x==y)return 0;
  if(!x.yy&&!y.yy)return 0;
  if(!x.yy){
    if(x.xx<=y.xx)return 0;

    /*
       ans->t
       cur->s

       ans
       xxxxxxx
       ans,cur
       xxxx____


       lcp::
       t s
       */
    /*
       ab

       t  ab 
       s  aaa
       0 1
       2 0
       ab
       ()aaa
       */

    const int lcp=min(Z::ext[y.xx],x.xx-y.xx);
    if(lcp==x.xx-y.xx)return 0;
    return cmpc(Z::t[y.xx+lcp],Z::s[lcp]);
  }else{
    if(!y.yy){
      /*
         c
         cu
         0 1
         2 0
         */
      if(x.xx>=y.xx)return 0;
      int lcp=Z::ext[x.xx];
      //!!! not t[x]
      //but ext[x]!!!
      //printf("my lcp=%d will cmp(t[%d]=%c,s[%d]=%c)\n",lcp, y.xx+lcp,Z::t[y.xx+lcp],lcp,Z::s[lcp]);
      if(lcp==Z::n)return 0;
      return cmpc(Z::s[lcp],Z::t[x.xx+lcp]);
      /*
         xxx___
         xxxxxxx
         */
    }
    /*
       (empty)aaa
       ab    aaa

       xxx___
       xxxx___
       */
    //printf("Ext[%d]=%d\n",x.xx,Z::ext[x.xx]);
    int lcp=min(Z::ext[x.xx],min(y.xx-x.xx,Z::n));
    //printf("lcp=%d n=%d y-x=%d\n",lcp,Z::n,y.xx-x.xx);
    if(lcp==Z::n)return 0;

    if(lcp<y.xx-x.xx)return cmpc(Z::s[lcp],Z::t[x.xx+lcp]);
    //printf("lcp=min(%d,%d)\n",Z::n-y.xx+x.xx,Z::nxt[y.xx-x.xx]);
    lcp=min(Z::n-y.xx+x.xx,Z::nxt[y.xx-x.xx]);
    if(lcp==Z::n-y.xx+x.xx)return 0;
    return cmpc(Z::s[y.xx-x.xx+lcp],Z::s[lcp]);
  }


}

inline int cmp(int x,int y){
  return cmp(a[x],a[y]);
}

inline void ins(int id,int n){
  if(0)printf("===============================\nid=%d\n",id);
  Z::build(s[id],ans,n,l);
  vis.reset();
  for(int j=0;j<=k;j++)if(f[id+1][k-j]){
    if(ok[j]){vis[j]=1;a[j]=pii(j,0);}
    if(j>=n&&ok[j-n]){
      if(vis[j])
        a[j]=cmp(a[j],pii(j-n,1))<=0?a[j]:pii(j-n,1);
      else vis[j]=1,a[j]=pii(j-n,1);
    }
  }

  if(0)for(int i=0;i<=k;i++)if(vis[i])printf("i=%d %d:%d\n",i,a[i].first,a[i].second);

  t=0;
  for(int j=0;j<=k;j++)if(vis[j]){
    while(t&&cmp(st[t],j)>0)t--;
    if(!t||cmp(st[t],j)==0)st[++t]=j;
    if(0){
      printf("i=%d st:",j);
      for(int i=1;i<=t;i++)printf("%d ",st[i]);puts("");
    }
  }



  if(0){
    puts("-----\n");
    for(int i=0;i<=k;i++)if(vis[i])printf("i=%d %d:%d\n",i,a[i].xx,a[i].yy);
    printf("st:");
    for(int i=1;i<=t;i++)printf("%d ",st[i]);puts("");
  }

  l=st[t];
  if(a[l].yy)for(int j=0;j<n;j++)ans[a[l].xx+j]=s[id][j];

  ok.reset();
  while(t)ok[st[t--]]=1;


  //ans[l]='\0';printf("id=%d\nans=%s\n",id,ans);

}

int main(){
  scanf("%d%d",&n,&k);
  for(int i=1;i<=n;i++){
    scanf("%s",s[i]);
    len[i]=strlen(s[i]);
  }

  ok[0]=f[n+1][0]=1;
  for(int i=n;i;i--)
    f[i]=f[i+1]|f[i+1]<<len[i];

  for(int i=1;i<=n;i++)ins(i,len[i]);

  ans[k]='\0';
  printf("%s\n",ans);

  return 0;
}