题目描述

赛道设计师由奈正在制作一条新的卡丁车赛道。赛道是一块 $H\times W$ 的矩形网格。每个格子最终都必须放置一块道路砖；道路砖可能没有道路，也可能有直道、弯道、三叉路、十字路等形状。所有砖都可以旋转。其中有一种特殊的弯道砖称为 curly tile，它只连接两个相邻方向。

在本题输入中，已有的 curly tile 会用数字 1 到 4 表示，其连接方向分别为：

• 1：连接上方和左方；
• 2：连接下方和左方；
• 3：连接上方和右方；
• 4：连接下方和右方。

一个合法赛道要求每个非禁止格最终都放有砖，并且道路不能出现断头。也就是说，任意一块砖中伸出到相邻格子的道路，都必须与相邻格子中对应方向的道路相连；道路不能伸出棋盘边界，也不能通向禁止放砖的格子。

现在棋盘上已经固定放置了一些 curly tile。你可以在若干空格中额外放置 curly tile，然后提交方案。之后管理员会尽力用任意种类的道路砖填满剩余空格，使整张棋盘成为合法赛道。

你只能放置 curly tile，不能删除、替换或旋转已经固定的 curly tile。此外，有些格子禁止放任何砖，有些格子则强制必须放 curly tile。

请你求出在仍然存在某种管理员补全方式的前提下，整条赛道中 curly tile 的最大总数。注意，输出的是最终赛道中 curly tile 的总数，不只是你新放置的数量。如果无论如何都无法形成合法赛道，输出 -1。

输入格式

第一行包含两个整数 $H,W$，表示棋盘大小。

接下来 $H$ 行，每行包含 $W$ 个字符，描述棋盘：

• 1：已固定的 curly tile，连接上方和左方；
• 2：已固定的 curly tile，连接下方和左方；
• 3：已固定的 curly tile，连接上方和右方；
• 4：已固定的 curly tile，连接下方和右方；
• o：空格，但必须放置 curly tile；
• x：空格，但不能放置任何砖；
• .：没有额外限制的空格。

输出格式

输出一行一个整数，表示在可以被管理员补全为合法赛道的前提下，最终赛道中 curly tile 的最大总数。

如果不存在任何合法赛道，输出 -1。

数据范围

• $1\le H,W\le 100$。

样例 1

输入

4 5
4...x
.2..2
.o1x.
3..3o

输出

12

样例 2

输入

2 3
4o2
3x1

输出

-1

样例说明

下图展示了样例 1 的初始棋盘状态。 下图展示了样例 1 的一种最优最终状态。其中，管理员放置的拼块用黄色标出。