You are given n non-decreasing arrays of non-negative numbers. 

Vasya repeats the following operation k times: 

  * Selects a non-empty array. 
  * Puts the first element of the selected array in his pocket. 
  * Removes the first element from the selected array. 



Vasya wants to maximize the sum of the elements in his pocket.

Input

The first line contains two integers n and k (1 ≤ n, k ≤ 3 000): the number of arrays and operations.

Each of the next n lines contain an array. The first integer in each line is t_i (1 ≤ t_i ≤ 10^6): the size of the i-th array. The following t_i integers a_{i, j} (0 ≤ a_{i, 1} ≤ … ≤ a_{i, t_i} ≤ 10^8) are the elements of the i-th array.

It is guaranteed that k ≤ ∑_{i=1}^n t_i ≤ 10^6.

Output

Print one integer: the maximum possible sum of all elements in Vasya's pocket after k operations.

Example

Input


3 3
2 5 10
3 1 2 3
2 1 20


Output


26
#include <bits/stdc++.h>
using namespace std;
template <class T>
void cmax(T& _, T __) {
  if (_ < __) _ = __;
}
template <class T>
void cmin(T& _, T __) {
  if (_ > __) _ = __;
}
namespace FastIO {
char iB[1 << 20], _d[45], *_s = nullptr, *_t = nullptr, oB[1 << 18], *_o = oB;
int read(char* x) {
  char ch = (_s == _t && (_t = (_s = iB) + fread(iB, 1, 1 << 20, stdin)),
             _s == _t ? EOF : *_s++),
       *p = x;
  while (~ch && ch <= ' ')
    ch = (_s == _t && (_t = (_s = iB) + fread(iB, 1, 1 << 20, stdin)),
          _s == _t ? EOF : *_s++);
  while (ch > ' ') {
    *p++ = ch,
    ch = (_s == _t && (_t = (_s = iB) + fread(iB, 1, 1 << 20, stdin)),
          _s == _t ? EOF : *_s++);
  }
  *p = '\0';
  return p - x;
}
template <class T>
bool read(T& x) {
  x = 0;
  if (!read(_d)) return 0;
  for (char* p = _d + (*_d == '-'); *p;) {
    x = x * 10 + (*p++ ^ 48);
  }
  if (*_d == '-') {
    x = -x;
  }
  return 1;
}
void flush() {
  fwrite(oB, 1, _o - oB, stdout);
  _o = oB;
}
void print(char x) {
  *_o++ = x;
  if (_o - oB > 262094) flush();
}
template <class T>
void print(T x) {
  if (x < 0) {
    *_o++ = '-', x = -x;
  }
  char* p = _d;
  if (!x) {
    print('0');
    return;
  }
  for (; x; x /= 10) *p++ = x % 10 + 48;
  while (p != _d) {
    *_o++ = *--p;
  }
  if (_o - oB > 262094) flush();
}
template <class T>
void print(T* x) {
  for (int i = 0; x[i];) print(x[i++]);
}
template <class T, class... A>
bool read(T& x, A&... r) {
  return read(x) && read(r...);
}
template <class T, class... A>
void print(T x, A... r) {
  print(x), print(r...);
}
template <class... A>
void println(A... r) {
  print(r...), print('\n');
}
}  // namespace FastIO
using namespace FastIO;
const int maxn = 3e3 + 10, INF = 0x3f3f3f3f;
const long long LINF = (long long)INF << 32 | INF, mod = 1e9 + 7;
long long dp[20][maxn], n, k, ans;
vector<long long> a[maxn];
void update(int d, int l, int r) {
  for (decltype(l) i = l; i <= (r); ++i)
    for (int j = k; j >= (int)a[i].size(); j--)
      cmax(dp[d][j], dp[d][j - a[i].size()] + a[i].back());
}
void solve(int d, int l, int r) {
  if (l == r) {
    cmax(ans, dp[d][k]);
    for (decltype(0) i = 0; i < ((int)a[l].size()); ++i)
      cmax(ans, dp[d][k - i - 1] + a[l][i]);
    return;
  }
  int mid = (l + r) >> 1;
  memcpy(dp[d + 1], dp[d], sizeof(long long) * (k + 1));
  update(d + 1, l, mid);
  solve(d + 1, mid + 1, r);
  memcpy(dp[d + 1], dp[d], sizeof(long long) * (k + 1));
  update(d + 1, mid + 1, r);
  solve(d + 1, l, mid);
}
int main() {
  read(n, k);
  for (decltype(1) i = 1; i <= (n); ++i) {
    int t;
    read(t);
    a[i].assign(t, 0);
    for (decltype(0) j = 0; j < (t); ++j) read(a[i][j]);
    for (decltype(1) j = 1; j < (t); ++j) a[i][j] += a[i][j - 1];
    if (t > k) a[i].resize(k);
  }
  solve(1, 1, n);
  println(ans);
  FastIO::flush();
  return 0;
}
