P7129 "RdOI R1" Ice Cream Game (play)

There is a new game to play again.

Little T found that a new game has appeared on the market recently. This game has $n$ levels. Playing level $i$ once costs $s_i$ stamina, and you can play level $i$ at most $m_i$ times. To play level $i$, you must have played level $i-1$ at least once. Of course, playing level $1$ does not require this prerequisite. The rules are as follows (for level $i$): There are $k_i$ ice creams in a row. The deliciousness of the $j$-th ice cream is $y_{i,j}$. Each time you need to choose one ice cream to eat, for a total of $k_i$ times. On the $j$-th time, if you eat the $l$-th ice cream, you gain $j\times y_{i,l}$ points. Of course, eating ice cream is not that easy. On the first time, you must eat the specified $c_i$-th ice cream. After that, each time you can only eat an ice cream at either end of the already eaten segment. For example, if you first eat the $2$-nd ice cream, then the second time you can eat the $1$-st or the $3$-rd one (if it exists). Since Little T is not good enough at computing these complicated scores, he wants to ask for your help. Under the condition that the stamina used does not exceed $t$, what is the maximum score he can obtain?

The first line contains two integers $n,t$, representing the number of levels and the amount of stamina. The next lines from line $2$ to line $2\times n+1$ describe the levels. For level $i$, line $2\times i$ and line $2\times i+1$ describe level $i$. Line $2\times i$ contains four integers $s_i,m_i,k_i,c_i$, as described in the statement. Line $2\times i+1$ contains $k_i$ integers. The $j$-th integer is $y_{i,j}$, as described in the statement.

Output one integer in a single line: the maximum score obtainable with stamina used not exceeding $t$.

[Sample Explanation] Sample 1: The optimal solution is to play level 1 once and then play level 2 once. In level 1, eat the ice creams in the order of the $2,3,4,1$-st. You can get $2\times 1+4\times 2+1\times 3+3\times 4=2+8+3+12=25$ points. In level 2, eat the ice creams in the order of the $3,4,2,1$-st. You can get $2\times 1+2\times 2+3\times 3+2\times 4=2+4+9+8=23$ points. So the maximum total score is $25\times 1+23\times 1=48$. Sample 2: The optimal solution is to play level 1 twice, level 2 once, and level 3 once. You can get $10000 \times 2+1 \times 1+2 \times 1=20003$ points. --- [Constraints] For $10\%$ of the testdata, $1 \le n \le 10 , 1 \le k_i,m_i,s_i,y_{i,j} \le 100 , 1 \le t \le 100$. For another $40\%$ of the testdata, $1 \le n \le 100 , 1 \le k_i,m_i,s_i,y_{i,j} \le 100 , 1 \le t \le 10^4$. For $100\%$ of the testdata, $1 \le n \le 200 , 1 \le k_i,m_i,s_i,y_{i,j} \le 500,1 \le t \le 10^5,1\le c_i\le k_i$. --- [Notes / Hints] - Try to understand the samples. --- [File Input/Output] **(Simulation, not required when submitting code)** - Filename: `play.cpp` - Input filename: `play.in` - Output filename: `play.out` Translated by ChatGPT 5