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 N = 3010;
const long long mod = 998244353;
long long a[N][N];
int l[N];
long long dp[N][N];
long long dp1[N][N];
long long S[N];
bool take[N][N];
void solve() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> l[i];
    long long sum = 0ll;
    for (int j = 1; j <= l[i]; j++) {
      int x;
      cin >> x;
      if (j <= k) {
        a[i][j] = x;
        sum += x;
      }
    }
    l[i] = min(l[i], k);
    S[i] = sum;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < l[i]; j++) dp[i][j] = dp[i - 1][j], take[i][j] = false;
    for (int j = k; j >= l[i]; j--) {
      dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - l[i]] + S[i]);
      if (dp[i - 1][j] > dp[i - 1][j - l[i]] + S[i])
        take[i][j] = false;
      else
        take[i][j] = true;
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = 0; j < l[i]; j++) dp1[i][j] = dp1[i + 1][j];
    for (int j = k; j >= l[i]; j--) {
      dp1[i][j] = max(dp1[i + 1][j], dp1[i + 1][j - l[i]] + S[i]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= k; j++) {
      a[i][j] += a[i][j - 1];
    }
  }
  long long res = dp[n][k];
  for (int it = 1; it <= k; it++) {
    vector<int> v, u;
    int cur = it;
    for (int i = n; i >= 1; i--) {
      if (take[i][cur]) {
        v.push_back(i);
        cur -= l[i];
      } else {
        u.push_back(i);
      }
    }
    for (int i : u) {
      if (k - it <= l[i]) res = max(res, dp[n][it] + a[i][k - it]);
    }
    for (int i : v) {
      int tk = k - it;
      if (tk > l[i]) continue;
      for (int j = 0; j <= it; j++) {
        res = max(res, a[i][tk] + dp[i - 1][j] + dp1[i + 1][it - j]);
      }
    }
  }
  cout << res << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  while (tt--) {
    solve();
  }
  return 0;
}
