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
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        int n;
        int k;
        int[][] a;
        long ans;

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            n = in.nextInt();
            k = in.nextInt();
            a = new int[n][];
            for (int i = 0; i < n; i++) {
                int t = in.nextInt();
                a[i] = new int[Math.min(k, t)];
                for (int j = 0; j < t; j++) {
                    int x = in.nextInt();
                    if (j < a[i].length) {
                        a[i][j] = x;
                    }
                }
            }

            solve(0, n, new long[k + 1]);
            out.println(ans);
        }

        private void solve(int l, int r, long[] dp) {
            if (l + 1 == r) {
                long sum = 0;
                long[] f = new long[dp.length];
                f[0] = dp[0];
                for (int i = 1; i < f.length; i++) {
                    f[i] = Math.max(f[i - 1], dp[i]);
                }
                for (int i = 0; i < a[l].length && i <= k; i++) {
                    ans = Math.max(ans, f[k - i] + sum);
                    sum += a[l][i];
                }
                ans = Math.max(ans, sum);
                return;
            }
            int m = (l + r) / 2;
            long[] saved = dp.clone();
            for (int i = l; i < m; i++) {
                long sum = 0;
                for (long x : a[i]) {
                    sum += x;
                }
                add(dp, a[i].length, sum);
            }
            solve(m, r, dp);
            System.arraycopy(saved, 0, dp, 0, saved.length);
            for (int i = m; i < r; i++) {
                long sum = 0;
                for (long x : a[i]) {
                    sum += x;
                }
                add(dp, a[i].length, sum);
            }
            solve(l, m, dp);
            System.arraycopy(saved, 0, dp, 0, saved.length);
        }

        private void add(long[] dp, int am, long sum) {
            for (int i = dp.length - 1 - am; i >= 0; i--) {
                dp[i + am] = Math.max(dp[i + am], dp[i] + sum);
            }
        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

