Description

李田所来到了一座荒岛上，荒岛可以看成n 行m 列的二维数组。

根据藏宝图所示,荒岛上有宝藏,李田所需要尽可能多地获取宝藏，地图上每个点都用一个大写字母表示,其中A 、C 、M 分别表示该点的价值为3 、2 、1 ，其余字母均无价值。

李田所从地图的左上角**(1，1)** 出发，前往地图的右下角**(n，m)** ，他每次只能 朝下 或朝右 移动，并且不能 移动出地图边界。

请聪明的你帮助一下李田所，求出他最多 能获得的宝物价值。

Format

Input

第一行输入n，m（1 ≤ n,m ≤ 500） ，表示地图有n 行m 列。

接下来n 行，每行m 个字母（保证输入为大写 ）。

Output

输出一个整数，表示可能获得最大 的价值。

Samples

4 3
ABM
ASC
BNY
CMD

9

Hint

在样例1 中：

选择路线**(1,1)→(2,1)→(3,1)→(4,1)→(4,2)→(4,3)**