题目描述

Josefine 正在玩一个类似俄罗斯方块的游戏，叫做 Bricks。

游戏区域是一个 $6$ 列、$8$ 行的矩形网格。一个砖块占据网格中的一个 $1\times 1$ 单元格。初始时网格为空。

一个砖块形状是一个矩形，其中某些位置是砖块，另一些位置是空气。例如，下面是一个 $4\times 3$ 的砖块形状，其中 # 表示砖块，_ 表示空气：

#_##
##__
#__#

游戏共有 $N$ 轮。每一轮，玩家会看到一个砖块形状，并需要决定把它从顶部的哪个水平位置落下。

落下时，形状中的每个砖块会独立地沿竖直方向下落，直到落在网格底部，或者落在另一个砖块正上方。这里与普通俄罗斯方块不同：砖块是独立下落的，因此每一列中不会留下空洞。

在落下之前，玩家可以将砖块形状旋转 $0^\circ$、$90^\circ$、$180^\circ$ 或 $270^\circ$。落下后，所有砖块必须位于网格内部。

每一轮结束时，所有砖块数量至少为 $3$ 的列都会坍塌，该列中的砖块会被移除。

第 $i$ 轮有一个分数系数 $s_i$。设第 $i$ 轮坍塌的砖块数为 $b_i$，则这一轮得分为：

请你计算，在所有轮中合理选择旋转方式和落下位置，最多可以获得多少总分。

输入格式

第一行一个整数 $N$，表示轮数。

接下来依次给出每一轮的信息。

每一轮第一行包含三个整数：

分别表示当前砖块形状的宽度、高度和本轮分数系数。

接下来 $h_i$ 行，每行一个长度为 $w_i$ 的字符串，由 # 和 _ 组成，描述当前砖块形状。

输入保证给出的矩形是能够覆盖所有砖块的最小矩形。

输出格式

输出一个整数，表示能够获得的最大总分。

数据范围

子任务

样例输入

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

样例输出

30

样例解释

一种最优方案可以在第二轮得到 $16$ 分，在第三轮得到 $14$ 分，总分为 $30$。