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 GCC optimize("O3")
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios {
  fast_ios() {
    cin.tie(nullptr), ios::sync_with_stdio(false),
        cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T, typename V>
void ndarray(vector<T> &vec, const V &val, int len) {
  vec.assign(len, val);
}
template <typename T, typename V, typename... Args>
void ndarray(vector<T> &vec, const V &val, int len, Args... args) {
  vec.resize(len),
      for_each(begin(vec), end(vec), [&](T &v) { ndarray(v, val, args...); });
}
template <typename T>
bool chmax(T &m, const T q) {
  if (m < q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T>
bool chmin(T &m, const T q) {
  if (m > q) {
    m = q;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) {
  return make_pair(l.first + r.first, l.second + r.second);
}
template <typename T1, typename T2>
pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) {
  return make_pair(l.first - r.first, l.second - r.second);
}
template <typename T>
vector<T> srtunq(vector<T> vec) {
  sort(vec.begin(), vec.end()),
      vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return vec;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << '[';
  for (auto v : vec) os << v << ',';
  os << ']';
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &vec) {
  os << "deq[";
  for (auto v : vec) os << v << ',';
  os << ']';
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &vec) {
  os << '{';
  for (auto v : vec) os << v << ',';
  os << '}';
  return os;
}
template <typename T, typename TH>
ostream &operator<<(ostream &os, const unordered_set<T, TH> &vec) {
  os << '{';
  for (auto v : vec) os << v << ',';
  os << '}';
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &vec) {
  os << '{';
  for (auto v : vec) os << v << ',';
  os << '}';
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) {
  os << '{';
  for (auto v : vec) os << v << ',';
  os << '}';
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &pa) {
  os << '(' << pa.first << ',' << pa.second << ')';
  return os;
}
template <typename TK, typename TV>
ostream &operator<<(ostream &os, const map<TK, TV> &mp) {
  os << '{';
  for (auto v : mp) os << v.first << "=>" << v.second << ',';
  os << '}';
  return os;
}
template <typename TK, typename TV, typename TH>
ostream &operator<<(ostream &os, const unordered_map<TK, TV, TH> &mp) {
  os << '{';
  for (auto v : mp) os << v.first << "=>" << v.second << ',';
  os << '}';
  return os;
}
constexpr int KMAX = 3001;
int main() {
  int N, K;
  cin >> N >> K;
  vector<vector<int>> A(N);
  vector<int> sz(N);
  vector<lint> tot(N);
  for (int i = (0), i_end_ = (N); i < i_end_; i++) {
    int t;
    cin >> t;
    A[i].resize(t);
    cin >> A[i];
    if (int(A[i].size()) > K) {
      A[i].resize(K);
    }
    sz[i] = A[i].size();
    tot[i] = accumulate((A[i]).begin(), (A[i]).end(), 0LL);
  }
  if (N == 1) {
    cout << accumulate(A[0].begin(), A[0].begin() + K, 0LL) << endl;
    return 0;
  }
  constexpr lint INF = 2e18;
  using arr = array<lint, KMAX>;
  vector<arr> dp;
  dp.reserve(N);
  dp.emplace_back(arr());
  fill((dp[0]).begin(), (dp[0]).end(), -INF);
  dp[0][0] = 0;
  auto ad = [&](int i) -> void {
    arr a = dp.back();
    for (int k = (K + 1 - sz[i]) - 1, k_begin_ = (0); k >= k_begin_; k--) {
      if (a[k] >= 0) {
        chmax(a[k + sz[i]], a[k] + tot[i]);
      }
    }
    dp.emplace_back(a);
  };
  constexpr int C = 75;
  lint ret = 0;
  for (int b = (0), b_end_ = ((N + C - 1) / C); b < b_end_; b++) {
    dp.resize(1);
    int l = b * C, r = min(N, (b + 1) * C);
    for (int i = (0), i_end_ = (N); i < i_end_; i++) {
      if (i < l or i >= r) {
        ad(i);
      }
    }
    for (int i = (l), i_end_ = (r); i < i_end_; i++) {
      for (int j = (i + 1), j_end_ = (r); j < j_end_; j++) {
        ad(j);
      }
      lint acc = 0;
      for (int n = (0), n_end_ = (sz[i]); n < n_end_; n++) {
        acc += A[i][n];
        chmax(ret, acc + dp.back()[K - n - 1]);
      }
      for (int j = (i + 1), j_end_ = (r); j < j_end_; j++) {
        dp.pop_back();
      }
      ad(i);
    }
  }
  cout << ret << '\n';
}
