题目描述

题目译自 NordicOI 2020 T2 「Bricks」

Josefine 正在玩一个类似俄罗斯方块的游戏 Bricks。游戏在一个 $6$ 列 $8$ 行的矩形网格中进行。一个砖块占据网格中的一个 $1 \times 1$ 的位置。最初网格是空的。一个砖块阵型是一个矩形，其中一些部分被砖块填充，其他部分是空的。以下是一个 $4 \times 3$ 的砖块阵型示例，其中 # 代表砖块，_ 代表空气：

#_##
##__
#__#

游戏进行 $N$ 轮。在每一轮中，玩家会看到一个砖块阵型，她必须决定从网格顶部的哪个位置（水平）掉落砖块阵型。当掉落砖块阵型时，每个砖块会独立地垂直下落，最终落在网格底部或另一个砖块上（来自同一阵型或之前的轮次）。由于砖块独立下落，列中不会有空气洞（这与俄罗斯方块不同）。在掉落砖块阵型之前，玩家可以将其旋转 $0$、$90$、$180$ 或 $270$ 度。砖块阵型必须在所有砖块都落在网格内的情况下掉落。

在每一轮结束时，网格中至少有 $3$ 个砖块的所有列会坍塌，砖块因此从网格中移除。第 $i$ 轮有一个关联的轮次得分 $s_i$。设第 $i$ 轮中坍塌的砖块数量为 $b_i$，则玩家在该轮中获得 $b_i \cdot s_i$ 分。

游戏的目标是最大化所有轮次的得分（即最大化 $\sum_{i=1}^{N} b_i s_i$）。通过编写一个程序，帮助 Josefine 计算给定 $N$ 个砖块阵型和轮次得分的情况下，可能获得的最高得分。

输入格式

第一行输入包含一个整数 $N$ $(1 \leq N \leq 300)$，表示轮次的数量。

接下来是每一轮的信息。每轮的第一行包含三个整数 $w_i, h_i, s_i$ $(1 \leq w_i, h_i \leq 6, 0 \leq s_i \leq 10000)$，分别表示第 $i$ 轮砖块阵型的宽度、高度和轮次得分。接下来的 $h_i$ 行每行包含一个长度为 $w_i$ 的字符串，由 #（砖块）或 _（空气）组成，描述第 $i$ 轮的砖块阵型。矩形总是覆盖阵型中所有砖块的最小可能矩形。

输出格式

输出一个整数，表示可能获得的最高得分。

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

30

如果我们将第一个砖块阵型尽可能向左掉落而不旋转，我们得到：

______
______
______
______
______
______
#_____
##____

然后我们将第二个砖块阵型逆时针旋转 $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$ 分。这是最优的。

数据范围与提示

详细子任务附加限制及分值如下表所示。