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;
using pii = pair<long long, long long>;
using pdd = pair<double, double>;
using pddi = tuple<double, double, long long>;
const long long MAXN = 3005;
long long K;
vector<long long> v[MAXN];
vector<long long> vp[MAXN];
long long w[MAXN];
void add(long long val, long long cnt, vector<long long> &v) {
  for (long long i = K; i >= 0; i--)
    if (i + cnt <= K) v[i + cnt] = max(v[i + cnt], v[i] + val);
}
long long ANS;
void solve(long long i, long long j, vector<long long> vk) {
  if (i == j) {
    for (long long k = 0; k <= K && k <= v[i].size(); k++)
      ANS = max(ANS, vk[K - k] + vp[i][k]);
    return;
  }
  long long m = (i + j) / 2;
  vector<long long> plvk = vk, prvk = vk;
  for (long long k = i; k <= m; k++) add(w[k], v[k].size(), plvk);
  for (long long k = m + 1; k <= j; k++) add(w[k], v[k].size(), prvk);
  solve(i, m, prvk), solve(m + 1, j, plvk);
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  long long n, k;
  cin >> n >> k;
  for (long long i = 0; i < n; i++) {
    long long xn;
    cin >> xn;
    v[i].resize(xn);
    for (long long &x : v[i]) cin >> x;
    vp[i].resize(xn + 2);
    for (long long j = 1; j <= xn; j++) vp[i][j] = vp[i][j - 1] + v[i][j - 1];
    w[i] = vp[i][xn];
  }
  K = k;
  solve(0, n - 1, vector<long long>(K + 2));
  cout << ANS << '\n';
}
