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;
template <typename T>
vector<T>& operator--(vector<T>& v) {
  for (auto& i : v) --i;
  return v;
}
template <typename T>
vector<T>& operator++(vector<T>& v) {
  for (auto& i : v) ++i;
  return v;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (auto& i : v) is >> i;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
  for (auto& i : v) os << i << ' ';
  return os;
}
template <typename T, typename U>
istream& operator>>(istream& is, pair<T, U>& p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& p) {
  os << p.first << ' ' << p.second;
  return os;
}
template <typename T, typename U>
pair<T, U> operator-(pair<T, U> a, pair<T, U> b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
template <typename T, typename U>
pair<T, U> operator+(pair<T, U> a, pair<T, U> b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
template <typename T, typename U>
void umin(T& a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
void umax(T& a, U b) {
  if (a < b) a = b;
}
int a[3005][3005];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, k;
  cin >> n >> k;
  vector<int> sz(n);
  for (int i = 0; i < n; ++i) {
    int t;
    cin >> t;
    for (int j = 0; j < t; ++j) {
      int u;
      cin >> u;
      if (j <= k) a[i][j] = u;
    }
    sz[i] = min(k, t);
  }
  vector<vector<long long>> pref(n);
  for (int i = 0; i < n; ++i) {
    pref[i].reserve(sz[i]);
    pref[i].push_back(a[i][0]);
    for (int j = 1; j < sz[i]; ++j) {
      pref[i].push_back(pref[i].back() + a[i][j]);
    }
  }
  vector<vector<long long>> pos(n, vector<long long>(k + 1));
  vector<pair<long long, int>> v;
  v.reserve(n + k);
  for (int ln = 1; ln <= k; ++ln) {
    v.clear();
    for (int i = 0; i < n; ++i) {
      if (pref[i].size() >= ln) v.emplace_back(pref[i][ln - 1], i);
    }
    sort(v.rbegin(), v.rend());
    for (int i = 0; i < v.size(); ++i) {
      pos[v[i].second][ln] = i;
    }
  }
  vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
  for (int i = 0; i < n; ++i) {
    long long sm = pref[i].back();
    dp[i + 1] = dp[i];
    for (int j = k - (int)sz[i]; j >= 0; --j) {
      dp[i + 1][j + sz[i]] = max(dp[i + 1][j + sz[i]], dp[i][j] + sm);
    }
    for (int ln = 1; ln <= sz[i]; ++ln) {
      int cbefore = pos[i][ln - 1] * ln;
      if (cbefore > k) continue;
      for (int j = 0; j + ln <= k; ++j)
        dp[i + 1][j + ln] = max(dp[i + 1][j + ln], dp[i][j] + pref[i][ln - 1]);
    }
  }
  cout << dp[n][k] << '\n';
  return 0;
}
