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;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
mt19937 rng((int)chrono::steady_clock::now().time_since_epoch().count());
const int MAX = 3000 + 10;
int n, k, t[MAX];
vector<long long> a[MAX];
vector<long long> memo[MAX];
void calc(int l, int r, vector<long long> curr) {
  if (l > r) return;
  if (l == r) {
    memo[l] = curr;
    return;
  }
  int m = (l + r) / 2;
  vector<long long> curr_l = curr, curr_r = curr;
  for (int i = l; i <= m; i++) {
    for (int j = k; j >= t[i]; j--) {
      curr_r[j] = max(curr_r[j], curr_r[j - t[i]] + a[i].back());
    }
  }
  for (int i = m + 1; i <= r; i++) {
    for (int j = k; j >= t[i]; j--) {
      curr_l[j] = max(curr_l[j], curr_l[j - t[i]] + a[i].back());
    }
  }
  calc(l, m, curr_l);
  calc(m + 1, r, curr_r);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> t[i];
    vector<long long> b(t[i]);
    for (long long &j : b) cin >> j;
    while (b.size() > k) b.pop_back();
    partial_sum(b.begin(), b.end(), back_inserter(a[i]));
  }
  vector<long long> curr(k + 1, 0);
  calc(0, n - 1, curr);
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= min(k, t[i]); j++) {
      ans = max(ans, memo[i][k - j] + (j != 0 ? a[i][j - 1] : 0LL));
    }
  }
  cout << ans << '\n';
  exit(0);
}
