P7129 「RdOI R1」冰淇淋游戏(play)

又有新游戏可玩啦！

小 T 发现最近市面上出现了一款游戏，这款游戏分为 $n$ 关，第 $i$ 关玩一次需要 $s_i$ 个体力，最多可以玩 $m_i$ 次第 $i$ 关。想玩第 $i$ 关，必须先玩第 $i-1$ 关至少一次，当然，玩第 $1$ 关不需要这个先决条件。 游戏规则是这样的（对于第 $i$ 关）： 一共有 $k_i$ 个冰淇淋排成一排，第 $j$ 个冰淇淋的美味度为 $y_{i,j}$，每次你需要选择一个冰淇淋吃掉，共吃 $k_i$ 次，在第 $j$ 次吃第 $l$ 个冰淇淋可以获得 $j\times y_{i,l}$ 分。 当然，要想吃冰淇淋可没有那么简单，你需要在第一次吃指定的第 $c_i$ 个冰淇淋，接下来每次只能吃已经吃完的段的两边的冰淇淋，比如第一次吃的是第 $2$ 个冰淇淋，第二次可以吃第 $1$ 个或第 $3$ 个（如果有的话）。 因为小 T 的脑子不太够计算这复杂的分数，所以他想求助你，在使用体力不超过 $t$ 的情况下，最多可以获得多少分数。

第一行有两个整数 $n,t$，分别表示关卡数和体力数。 接下来第 $2$ 到第 $2\times n+1$ 行，第 $2\times i$ 行和第 $2\times i+1$ 行描述第 $i$ 关。 第 $2\times i$ 行四个整数 $s_i,m_i,k_i,c_i$，意义见题面。 第 $2\times i+1$ 行 $k_i$ 个整数，第 $j$ 个为 $y_{i,j}$，意义见题面。

一行一个整数，为使用体力不超过 $t$ 的情况下的获得的分数的最大值。

【样例解释】 样例1： 最优解为玩一次第一关再玩一次第二关。 第一关按照第 $2,3,4,1$ 个的顺序吃冰淇淋，可以获得 $2\times 1+4\times 2+1\times 3+3\times 4=2+8+3+12=25$ 的分数。 第二关按照第 $3,4,2,1$ 个的顺序吃冰淇淋，可以获得 $2\times 1+2\times 2+3\times 3+2\times 4=2+4+9+8=23$ 的分数。 所以最多可以获得 $25\times 1+23\times 1=48$ 的分数。 样例2： 最优解为玩两次第一关，一次第二关，一次第三关。 可以获得 $10000 \times 2+1 \times 1+2 \times 1=20003$ 的分数。 --- 【数据范围】 对于 $10\%$ 的数据，$1 \le n \le 10 , 1 \le k_i,m_i,s_i,y_{i,j} \le 100 , 1 \le t \le 100$。 对于另外 $40\%$ 的数据，$1 \le n \le 100 , 1 \le k_i,m_i,s_i,y_{i,j} \le 100 , 1 \le t \le 10^4$。 对于 $100\%$ 的数据，$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$。 --- 【说明/提示】 - 尝试理解样例 --- 【文件读入读出】**（模拟，提交代码时不需使用）** - 文件名：`play.cpp` - 读入文件名：`play.in` - 读出文件名：`play.out`