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>

#ifdef ONLINE_JUDGE
#define freopen \
  if (0) freopen
#define cerr \
  if (0) cerr
#endif

#define fi first
#define se second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)

#define sqr(a) ((a)*1ll * (a))
#define sz(a) (int)a.size()
#define len(a) (int)a.length()
#define all(a) a.begin(), a.end()
#define nl '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef pair<int, int> pi;

const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

int n, k;
string s[2020];
bool can[2020][10020], ok[2020][10020];
string ans;

vector<int> z_algo(string s) {
  vector<int> z(20020, 0);
  for (int i = 1, l = 0, r = 1; i < len(s); i++) {
    if (i >= r) {
      l = r = i;
      while (i + z[i] < len(s) && s[z[i]] == s[i + z[i]]) z[i]++, r++;
    } else if (r - i > z[i - l]) {
      z[i] = z[i - l];
    } else {
      z[i] = r - i;
      l = i;
      while (i + z[i] < len(s) && s[z[i]] == s[i + z[i]]) z[i]++, r++;
    }
  }
  return z;
}

void solve() {
  cin >> n >> k;
  rep(i, 1, n) { cin >> s[i]; }

  can[n + 1][0] = true;
  per(i, n, 1) {
    rep(j, 0, k) {
      if (!can[i + 1][j]) continue;
      can[i][j] = true;
      if (j + len(s[i]) > k) continue;
      can[i][j + len(s[i])] = true;
    }
  }

  ok[0][0] = true;
  ans = "";
  rep(i, 1, n) {
    int ans_prefix_len = -1;
    vector<int> z = z_algo(s[i] + ans);
    rep(j, 0, k) {
      if (!ok[i - 1][j]) continue;
      ok[i][j] = true;

      int new_len = j + len(s[i]);
      if (new_len > k) continue;
      if (!can[i + 1][k - new_len]) continue;

      // new_str = ans.substr(0, j) + s[i]
      // 1. new_str is prefix of ans - OK
      // 2. ans is prefix of new_str - OK, UPDATE ans
      // 3. new_str is higher than ans - SKIP
      // 4. new_str is lower than ans - RESET

      if (z[len(s[i]) + j] >= len(s[i])) {
        ok[i][new_len] = true;
      } else if (z[len(s[i]) + j] <= len(s[i]) &&
                 j + z[len(s[i]) + j] == len(ans)) {
        ok[i][new_len] = true;
        ans_prefix_len = j;
      } else if (s[i][z[len(s[i]) + j]] > ans[j + z[len(s[i]) + j]]) {
        continue;
      } else {
        int prefix_len = j + z[len(s[i]) + j];
        rep(l, 0, prefix_len) { ok[i][l] |= ok[i - 1][l]; }
        rep(l, prefix_len + 1, k) { ok[i][l] = false; }
        ok[i][new_len] = true;
        ans_prefix_len = j;

        break;
      }
    }

    if (ans_prefix_len != -1) {
      ans = ans.substr(0, ans_prefix_len) + s[i];
    }

    // cout << s[i] << "\t: ";
    // rep(j, 0, k) {
    //   if (ok[i][j]) cout << ans.substr(0, j) << ' ';
    // }
    // cout << nl;
  }
  cout << ans;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  freopen(".in", "r", stdin);

  solve();

  return 0;
}