题目背景

又有新游戏可玩啦！

题目描述

小 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$ 的情况下的获得的分数的最大值。

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

提示

【样例解释】

样例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