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;
  }

}

#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(x==y)return 0;
  if(!x.yy&&!y.yy)return 0;
  if(!x.yy){
    if(x.xx<=y.xx)return 0;
    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){
      if(x.xx>=y.xx)return 0;
      int lcp=Z::ext[x.xx];
      //!!! not t[x] but ext[x]!!!
      if(lcp==Z::n)return 0;
      return cmpc(Z::s[lcp],Z::t[x.xx+lcp]);
    }
    int lcp=min(Z::ext[x.xx],min(y.xx-x.xx,Z::n));
    if(lcp==Z::n)return 0;
    if(lcp<y.xx-x.xx)return cmpc(Z::s[lcp],Z::t[x.xx+lcp]);
    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){
  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);
    }
  }

  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))st[++t]=j;
  }

  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;

}

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]);

  printf("%s\n",ans);

  return 0;
}