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)