Description

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?

Input Format

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 Format

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

2 20
9 1 4 2
3 2 4 1
11 2 4 3
2 3 2 2

48

3 20
9 2 1 1
10000
1 4 1 1
1
1 4 1 1
2

20003

Hint

[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