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 <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}

#define INF 1e9+7
#define LLINF 1e18+7
#define N 250000
ll MOD=1e9+7;

int makeable[2010][10100];
vector<pair<string,int>> dp(10010,pair<string,int>{"{",-1});
vector<string> s;
vector<int> a;

int main(){
  int n=in(),k=in();
  set<char> T;
  rep(i,n){
    string S;cin>>S;
    s.pb(S);
    a.pb(S.size());
    for(auto e:S)T.insert(e);
  }
  if(T.size()==1){rep(i,k)cout<<s[0][0];return 0;}
  dp[0].first="";
  makeable[n][k]=1;
  rep3(i,n-1,0){
    int x=a[i];
    rep(j,k+1){
      makeable[i][j]=(makeable[i+1][j]|makeable[i+1][j+x]);
    }
  }
  /*
  rep(i,n+1){
    rep(j,k+1){
      cout<<makeable[i][j]<<" ";
    }
    cout<<endl;
  }
  */
  rep(i,k+1){
    string temp=dp[i].first;
    int index=dp[i].second;
    rep2(j,index+1,n-1){
      if(makeable[j][i]==0)continue;
      string t=temp+s[j];
      if(i+a[j]>k)continue;
      if(dp[i+a[j]].first>t){
        dp[i+a[j]].first=t;
        dp[i+a[j]].second=j;
      }
    }
    /*
    rep(i,k+1){
      cout<<dp[i].first<<" ";
    }
    cout<<endl;
    */
  }
  cout<<dp[k].first;
}