Josefine 正在玩一个类似俄罗斯方块的游戏，叫做“积木”（bricks）。游戏在一个 $6$ 列 $\times$ $8$ 行的矩形网格中进行。一块积木占用网格中的一个 $1 \times 1$ 格子。最初网格是空的。

一个“积木形状”是一个矩形，其中某些部分填充了积木，其余部分是空气。以下是一个 $4 \times 3$ 积木形状的示例，其中 # 代表积木，_ 代表空气：

#_##
##__
#__#

游戏共进行 $N$ 轮。在每一轮中，玩家会看到一个积木形状，她必须决定从网格顶部的哪个（水平）位置将其落下。当落下积木形状时，每块积木都会独立地沿垂直线向下掉落，并落到网格底部或直接落到另一块积木的顶部（该积木可以来自同一个形状，也可以来自之前的轮次）。由于积木是独立掉落的，因此之后同一列的积木之间不会留下任何空气孔洞（这与俄罗斯方块不同）。在落下积木形状之前，玩家可以将其旋转 0、90、180 或 270 度。积木形状在落下时，必须保证所有积木都落在网格内部。

在每一轮结束时，网格中所有包含至少 3 块积木的列都会坍塌，其中的积木随之从网格中移除。第 $i$ 轮有一个关联的单轮得分 $s_i$。设 $b_i$ 为第 $i$ 轮中坍塌的积木数量，玩家在该轮中将获得 $b_i \cdot s_i$ 分。

游戏的目标是最大化所有轮次的总得分（即最大化 $\sum_{i=1}^N b_i \cdot s_i$）。编写一个程序，在给定 $N$ 个积木形状和每轮得分的情况下，计算可以获得的最大可能得分，以此来帮助 Josefine。

输入格式

• 第一行：轮数 $N$（$1 \le N \le 300$）。
• 对于每一轮：
  • 下一行：整数 $w_i, h_i, s_i$，其中 $w_i \times h_i$ 是第 $i$ 个积木形状的尺寸，$s_i$ 是该轮的得分（$1 \le w_i, h_i \le 6$ 且 $0 \le s_i \le 10000$）。
  • 接下来的 $h_i$ 行：表示积木形状的 $w_i \times h_i$ 矩形，由 # 和 _ 组成，其中 # 代表积木，_ 代表空气。（该矩形总是覆盖形状中所有积木的最小可能矩形）。

输出格式

• 第一行：最大可能得分。

样例

输入样例 1

3
2 2 10
#_
##
3 2 4
#_#
_#_
3 3 2
#_#
###
#__

输出样例 1

30

说明

考虑上述包含 3 轮的输入：

如果我们直接将第一个积木形状在不旋转的情况下尽可能靠左落下，我们得到：

______
______
______
______
______
______
#_____
##____

如果我们随后将第二个积木形状逆时针旋转 90 度，并尽可能靠左落下，我们得到（X 表示坍塌的积木——它们将在下一轮开始前消失）：

______
______
______
______
X_____
X_____
X#____
X#____

由于第 2 轮的单轮得分为 4，我们从此轮中获得 $4 \cdot 4 = 16$ 分。

最后，我们将最后一个积木形状旋转 180 度，并将其落在左数第二列（即从左往右数第二个位置），我们得到：

______
______
______
______
_X____
_X_X__
_X_X__
_X#X__

最后一轮的单轮得分为 2，因此我们在这一轮中获得 $2 \cdot 7 = 14$ 分。

总共我们获得了 $0 + 16 + 14 = 30$ 分。这是最优解。

子任务

您的解法将在若干测试点结合上进行测试。要获得一个子任务的分数，您需要通过该子任务中的所有测试用例。