410714: GYM104090 C No Bug No Game

Putata is preparing the RPG Pro League (RPL) held by the International Computer Playing Company (ICPC). In this RPG game, the player will wear $$$n$$$ items at the same time. Each item can offer the player several points of power. There is a magic buff in the game, which can upgrade each item such that they can offer several points of bonus power.

However, the buff is limited, it can only buff at most $$$k$$$ points of power. Formally, assume the player is wearing nothing initially, and then will wear all the $$$n$$$ items one by one. The game server will scan through all these $$$n$$$ items one by one, according to the permutation that the player wears them. When the server is scanning the $$$i$$$-th item, which can offer $$$p_i$$$ points of power, let $$$sum=\sum_{1\leq j<i}p_j$$$ denoting the total points of power scanned before:

• If $$$sum+p_i\leq k$$$, the whole item will be upgraded. The buff will offer $$$w_{i,p_i}$$$ points of bonus power.
• If $$$sum\geq k$$$, the item won't be upgraded. The buff will offer nothing.
• Otherwise, only a part of the item will be upgraded. The buff will offer $$$w_{i,k-sum}$$$ points of bonus power.

Putata is clever, he soon realized that he can adjust the permutation to wear these $$$n$$$ items to gain more points of bonus power! Unfortunately, Putata doesn't know the optimal permutation, please write a program to help him.

The behavior of the magic buff performed by the game server is a bug. The game code can work all thanks to bugs, so it is possible that $$$w_{i,a}>w_{i,b}$$$ where $$$a<b$$$.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 3\,000$$$, $$$0\leq k\leq 3\,000$$$), denoting the number of items and the limit $$$k$$$.

Each of the following $$$n$$$ lines starts with an integer $$$p_i$$$ ($$$1\leq p_i\leq 10$$$), denoting the base power of the $$$i$$$-th item, followed by $$$p_i$$$ integers $$$w_{i,1},w_{i,2},\ldots,w_{i,p_i}$$$ ($$$1\leq w_{i,j}\leq 10^5$$$).

Output a single line containing an integer, denoting the maximum points of total bonus power that can be reached. The base power is not included in the answer.

4 5
2 1 3
2 1 1
2 3 1
2 1 3

9