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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const double PI = 2 * acos(0.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());
const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";
template <class T0, class T1>
inline ostream &operator<<(ostream &out, pair<T0, T1> &a) {
  return out << "{" << a.first << ", " << a.second << "}";
}
template <class T0, class T1>
inline istream &operator>>(istream &in, pair<T0, T1> &a) {
  return in >> a.first >> a.second;
}
template <class T0, class T1, class T2>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2> &a) {
  return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a)
             << "}";
}
template <class T0, class T1, class T2, class T3>
inline ostream &operator<<(ostream &out, tuple<T0, T1, T2, T3> &a) {
  return out << "{" << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a)
             << ", " << get<3>(a) << "}";
}
template <class T>
inline ostream &operator<<(ostream &out, vector<T> &a) {
  out << "[";
  for (int i = 0; i < int(a.size()); ++i)
    out << a[i] << vector<string>{", ", "]  "}[i + 1 == a.size()];
  return out;
}
void smain();
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout << setprecision(12) << fixed;
  smain();
  return 0;
}
const long double timelim = 1.4;
inline bool break_time(long double time = timelim) {
  return clock() > CLOCKS_PER_SEC * time;
}
const int N = 3030;
long long sum[N + N];
long long dp[N + N][N];
const int B = 77;
void smain() {
  int n, k;
  cin >> n >> k;
  vector<vector<long long> > a(n);
  for (int i = 0; i < n; ++i) {
    int s;
    cin >> s;
    a[i].resize(s);
    for (int j = 0; j < int(s); ++j) {
      cin >> a[i][j];
    }
    if (a[i].size() > k) {
      a[i].resize(k);
    }
  }
  vector<vector<long long> > tmp = a;
  a.insert(a.end(), tmp.begin(), tmp.end());
  vector<vector<long long> > pref(a.size());
  for (int i = 0; i < a.size(); ++i) {
    sum[i] = accumulate(a[i].begin(), a[i].end(), 0LL);
    pref[i].push_back(0);
    for (int j = 0; j < a[i].size(); ++j) {
      pref[i].push_back(pref[i].back() + a[i][j]);
    }
  }
  if (n == 1) {
    cout << pref[0].back();
    return;
  }
  int st = 0;
  long long ans = 0;
  while (st < n) {
    int prev = st;
    st += B;
    if (st >= n) st = n;
    for (int j = 0; j < int(k + 1); ++j) {
      dp[st - 1][j] = 0;
    }
    for (int i = st, j = n - 1; j--; ++i) {
      dp[i][0] = dp[i - 1][0];
      int s = a[i].size();
      for (int w = 1; w < s; ++w) {
        dp[i][w] = dp[i - 1][w];
      }
      for (int w = s; w <= k; ++w) {
        dp[i][w] = ((dp[i - 1][w]) > (dp[i - 1][w - s] + sum[i])
                        ? (dp[i - 1][w])
                        : (dp[i - 1][w - s] + sum[i]));
      }
    }
    int final = n + st - 2;
    int s;
    for (int i = st - 1; i >= prev; --i) {
      int layer = n + i;
      for (int j = layer, id = st - 1; j <= final; ++j, --id) {
        s = a[id].size();
        dp[j][0] = dp[j - 1][0];
        for (int w = 1; w < s; ++w) {
          dp[j][w] = dp[j - 1][w];
        }
        for (int w = s; w <= k; ++w) {
          dp[j][w] = ((dp[j - 1][w]) > (dp[j - 1][w - s] + sum[id])
                          ? (dp[j - 1][w])
                          : (dp[j - 1][w - s] + sum[id]));
        }
      }
      s = a[i].size();
      for (int mid = 0; mid <= s; ++mid) {
        ans = ((ans) > ((pref[i][mid] + dp[final][k - mid]))
                   ? (ans)
                   : ((pref[i][mid] + dp[final][k - mid])));
      }
    }
  }
  cout << ans;
}
