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 MAXN = 3000;
const long long INF = 1e18;
int N, K;
vector<long long> A[MAXN + 10];
vector<int> tree[MAXN * 4 + 10];
void update(int node, int tl, int tr, int l, int r, int p) {
  if (l <= tl && tr <= r) {
    tree[node].push_back(p);
    return;
  }
  if (r < tl || tr < l) return;
  int mid = tl + tr >> 1;
  update(node * 2, tl, mid, l, r, p);
  update(node * 2 + 1, mid + 1, tr, l, r, p);
}
long long dp[MAXN + 10];
long long ans;
void solve(int node, int tl, int tr) {
  if (tl == tr) {
    for (int i = 0; i <= K; i++) {
      if (i < A[tl].size())
        ans = max(ans, dp[K - i] + A[tl][i]);
      else
        ans = max(ans, dp[K - i]);
    }
    return;
  }
  int mid = tl + tr >> 1;
  vector<long long> memo(K + 1);
  for (int i = 0; i <= K; i++) memo[i] = dp[i];
  for (auto it : tree[node]) {
    long long v = A[it].back(), w = A[it].size() - 1;
    for (int i = K; i >= w; i--) dp[i] = max(dp[i], dp[i - w] + v);
  }
  solve(node * 2, tl, mid);
  solve(node * 2 + 1, mid + 1, tr);
  for (int i = 0; i <= K; i++) dp[i] = memo[i];
}
int main() {
  scanf("%d%d", &N, &K);
  for (int i = 1; i <= N; i++) {
    int t;
    scanf("%d", &t);
    A[i].push_back(0);
    while (t--) {
      long long p;
      scanf("%lld", &p);
      A[i].push_back(A[i].back() + p);
    }
  }
  for (int i = 2; i <= N; i++) update(1, 1, N, 1, i - 1, i);
  for (int i = 1; i < N; i++) update(1, 1, N, i + 1, N, i);
  dp[0] = 0;
  for (int i = 1; i <= K; i++) dp[i] = -INF;
  solve(1, 1, N);
  printf("%lld\n", ans);
}
