题目

蜗牛莎莉喜欢在一个 N×N 的方格矩阵中散步。

她每次都从左上角出发。

方格矩阵中有空地（用 . 表示）和障碍（用 # 表示）。

下面是一个具体示例：

          A B C D E F G H
        1 S . . . . . # .
        2 . . . . # . . .
        3 . . . . . . . .
        4 . . . . . . . .
        5 . . . . . # . .
        6 # . . . . . . .
        7 . . . . . . . .
        8 . . . . . . . .

莎莉只能沿着水平或垂直方向移动。

在开始时，她位于 A1 位置，并选择一个方向（向下或向右）开始移动。

她会一直沿着一个方向移动，直到遇到矩阵边缘或障碍。

这时，她将转向 90 度，继续前进。

她在移动过程中，不能走出矩阵，或走进有障碍的格子中，也不能走到之前走过的格子中。

当她无法进行任何移动时，行动结束。

以下是上述示例中莎莉的一种行走情况：

          A B C D E F G H
        1 S---------+ # .
        2 . . . . # | . .
        3 . . . . . | . .
        4 . . . . . +---+
        5 . . . . . # . |
        6 # . . . . . . |
        7 +-----------+ |
        8 +-------------+

莎莉沿着右，下，右，下，左，上，右的方向走到了 G7 的位置，此时她无法进行任何移动，行动停止。（前方是她走过的格子，不能进入，并且由于前方不是障碍且没有出界所以也不能转向）

给定具体的方格矩阵，请你帮莎莉找到一个最合理的行进路线，使得她可以经过的格子数量尽可能大。

输出可经过格子最大数量。

输入格式

第一行包含两个整数 N 和 B，分别表示矩阵尺寸以及障碍的数量。

接下来 B 行，每行描述一个障碍的具体位置，用如题面所示的字母和数字表示。

注意，当 N>26 时，输入中不会在 Z 列右侧设计障碍。

输出格式

输出一个整数，表示可经过格子的最大数量。

8 4
E2
A6
G1
F5

33

样例解释

一种最佳行进方式如下：

          A B C D E F G H
        1 S . . . . . # .
        2 | . . . # . . .
        3 | . . . +-----+
        4 | . . . | . . |
        5 +-------+ # . |
        6 # . . . . . . |
        7 +------------ |
        8 +-------------+

数据范围

$1<𝑁≤120$