#569. 「LibreOJ Round #11」Misaka Network 与测试

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cz_xuyixuan

题目描述

研究者们想要测试 Misaka Network,于是他们把 Misaka Network 中的所有妹妹们召集到了一起。

现在妹妹们排成了 NNMM 列,有的位置没有人。现在研究者们给每一个个体的超能力进行了评定,一共有三个能力等级:Level 1 低能力者Level 2 异能力者Level 3 超能力者。研究者们每次测试可以选取一个子矩形内的所有个体,为了保证高效,他们不希望这个矩形内存在空的位置。并且,为了保证稳定,他们希望这个矩形内所有个体的能力等级的平均值恰好为 22。同时,每个个体最多只能参加一次测试,因此,多次测试选取的矩形应当不相交。

研究者们想知道他们最多能进行多少次测试。

输入格式

第一行两个整数NNMM

接下来 NN 行每行 MM 个字符,每个字符表示了队列中对应位置的个体。

1 表示 Level 1 低能力者2 表示 Level 2 异能力者3 表示 Level 3 超能力者* 表示一个空的位置。

输出格式

一行一个整数,表示最多能够进行多少次测试。

样例

样例输入 1

2 3
31*
*13

样例输出 1

2

样例输入 2

6 6
23311*
**13**
11*233
13*223
***133
331***

样例输出 2

9

样例输入 3

2 50
21111121332233123311312211231333122233133212221212
21332123132223111331233121122331133311112121331311

样例输出 3

51

数据范围与提示

对于所有数据 1N×M1051 \leq N \times M \leq 10^5,队列中仅包含 123* 四种字符。

子任务编号分值N×MN \times M特殊性质
155105\leq 10^5队列中不存在 1
215151000\leq 1000N=1N=1
315152000\leq 2000N=2N=2
435352000\leq 2000队列中不存在 *
515152000\leq 2000-
61515105\leq 10^5-