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 = 3007;
bool allowed[N][N];
long long sum[N][N];
const long long INF = -1e18;
long long dp[N];
long long dp2[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<vector<int> > v(n);
  for (auto &first : v) {
    int t;
    cin >> t;
    first.assign(t, -1);
    for (auto &el : first) cin >> el;
  }
  int ta = 0;
  for (int len = 1; len <= k; ++len) {
    vector<pair<long long, int> > arr;
    for (int i = 0; i < n; ++i) {
      if (v[i].size() >= len) {
        sum[i][len] = sum[i][len - 1] + v[i][len - 1];
        arr.push_back(make_pair(sum[i][len], i));
      }
    }
    sort(arr.begin(), arr.end(), greater<pair<long long, int> >());
    int can = (k + 2 * len - 1) / len;
    ta += min((int)arr.size(), can);
    int u = 0;
    while (u < arr.size() && u < can) {
      allowed[arr[u++].second][len] = true;
    }
  }
  for (int i = 0; i < N; ++i) dp[i] = INF;
  dp[0] = 0;
  for (int i = 0; i < n; ++i) {
    allowed[i][0] = true;
    if (v[i].size() < N) allowed[i][v[i].size()] = true;
    for (int i = 0; i < N; ++i) dp2[i] = INF;
    for (int j = 0; j <= k; ++j) {
      if (allowed[i][j]) {
        for (int was = k - j; was >= 0; was--) {
          dp2[was + j] = max(dp2[was + j], dp[was] + sum[i][j]);
        }
      }
    }
    for (int i = 0; i < N; ++i) dp[i] = dp2[i];
  }
  cout << dp[k];
}
