Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

dp

greedy

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Sum

time limit per test

1.5 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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 \le n, k \le 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 \le t_i \le 10^6$$$): the size of the $$$i$$$-th array. The following $$$t_i$$$ integers $$$a_{i, j}$$$ ($$$0 \le a_{i, 1} \le \ldots \le a_{i, t_i} \le 10^8$$$) are the elements of the $$$i$$$-th array.

It is guaranteed that $$$k \le \sum\limits_{i=1}^n t_i \le 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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/21/2024 02:46:49 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|