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;
inline int read() {
  int x = 0;
  bool flg = false;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') flg = true;
  for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
  return flg ? -x : x;
}
const long long INF = 1e18;
int n, k, s[3010];
vector<long long> c[3010];
long long ans;
long long f[15][3010];
void solve(int l, int r, int d) {
  long long *F = f[d], *G = f[d + 1];
  if (l == r) {
    for (int i = 0; i <= k; i++)
      if (F[i] != -INF && k - i <= s[l]) {
        long long H = i == k ? 0 : c[l][k - i - 1];
        ans = max(ans, F[i] + H);
      }
    return;
  }
  int mid = l + r >> 1;
  for (int i = 0; i <= k; i++) G[i] = F[i];
  for (int i = mid + 1; i <= r; i++) {
    long long V = s[i], W = c[i][s[i] - 1];
    for (int j = k; j >= V; j--)
      if (G[j - V] != -INF) G[j] = max(G[j], G[j - V] + W);
  }
  solve(l, mid, d + 1);
  for (int i = 0; i <= k; i++) G[i] = F[i];
  for (int i = l; i <= mid; i++) {
    long long V = s[i], W = c[i][s[i] - 1];
    for (int j = k; j >= V; j--)
      if (G[j - V] != -INF) G[j] = max(G[j], G[j - V] + W);
  }
  solve(mid + 1, r, d + 1);
}
int main() {
  n = read(), k = read();
  for (int i = 1; i <= n; i++) {
    c[i].resize(s[i] = read());
    for (int j = 0; j < s[i]; j++) c[i][j] = read();
    for (int j = 1; j < s[i]; j++) c[i][j] += c[i][j - 1];
  }
  f[0][0] = 0;
  for (int i = 1; i <= k; i++) f[0][i] = -INF;
  solve(1, n, 0);
  cout << ans << endl;
  return 0;
}
