1 /*

  2 ID:zhangyi20

  3 PROG:snail

  4 LANG:C++

  5 */

  6 #include <iostream>

  7 #include <cstdio>

  8 #include <cmath>

  9 using namespace std;

 10 #define MaxN 120

 11 int N,B;

 12 int mat[MaxN+5][MaxN+5];//0空地 1障碍 2走过

 13 int Dfs(int i,int j,int Dir)//方向：0向上，1向右，2向下，3向左

 14 {

 15     mat[i][j]=2;

 16     int Ret=0,i_=i,j_=j;

 17     int tmp1=-1,tmp2=-1;

 18     if(Dir==0)//向上

 19     {

 20         for(i=i-1; ;--i,++Ret)

 21         {

 22             if(mat[i][j])

 23                 break;

 24             mat[i][j]=2;

 25         }

 26         if(mat[i][j]==1)//转向

 27         {

 28             if(mat[i+1][j-1])

 29                 tmp1=0;

 30             else

 31                 tmp1=Dfs(i+1,j,3);

 32             if(mat[i+1][j+1])

 33                 tmp2=0;

 34             else

 35                 tmp2=Dfs(i+1,j,1);

 36             Ret+=max(tmp1,tmp2);

 37         }

 38         for(i=i+1;i<=i_;++i)

 39             mat[i][j]=0;

 40     }

 41     else if(Dir==1)//向右

 42     {

 43         for(j=j+1; ;++j,++Ret)

 44         {

 45             if(mat[i][j])

 46                 break;

 47             mat[i][j]=2;

 48         }

 49         if(mat[i][j]==1)//转向

 50         {

 51             if(mat[i-1][j-1])

 52                 tmp1=0;

 53             else

 54                 tmp1=Dfs(i,j-1,0);

 55             if(mat[i+1][j-1])

 56                 tmp2=0;

 57             else

 58                 tmp2=Dfs(i,j-1,2);

 59                 Ret+=max(tmp1,tmp2);

 60         }

 61         for(j=j-1;j>=j_;--j)

 62             mat[i][j]=0;

 63     }

 64     else if(Dir==2)//向下

 65     {

 66         for(i=i+1; ;++i,++Ret)

 67         {

 68             if(mat[i][j])

 69                 break;

 70             mat[i][j]=2;

 71         }

 72         if(mat[i][j]==1)//转向

 73         {

 74             if(mat[i-1][j-1])

 75                 tmp1=0;

 76             else

 77                 tmp1=Dfs(i-1,j,3);

 78             if(mat[i-1][j+1])

 79                 tmp2=0;

 80             else

 81                 tmp2=Dfs(i-1,j,1);

 82             Ret+=max(tmp1,tmp2);

 83         }

 84         for(i=i-1;i>=i_;--i)

 85             mat[i][j]=0;

 86     }

 87     else//向左

 88     {

 89         for(j=j-1; ;--j,++Ret)

 90         {

 91             if(mat[i][j])

 92                 break;

 93             mat[i][j]=2;

 94         }

 95         if(mat[i][j]==1)//转向

 96         {

 97             if(mat[i-1][j+1])

 98                 tmp1=0;

 99             else

100                 tmp1=Dfs(i,j+1,0);

101             if(mat[i+1][j+1])

102                 tmp2=0;

103             else

104                 tmp2=Dfs(i,j+1,2);

105             Ret+=max(tmp1,tmp2);

106         }

107         for(j=j+1;j<=j_;++j)

108             mat[i][j]=0;

109     }

110     return Ret;

111 }

112 int main()

113 {

114     freopen("snail.in","r",stdin);

115     freopen("snail.out","w",stdout);

116     scanf("%d%d",&N,&B);

117     int i,j;

118     char c;

119     for(i=1;i<=B;++i)

120     {

121         do

122         {

123             scanf("%c",&c);

124         }while(c<'A'||c>'Z');

125         scanf("%d",&j);

126         mat[j][c-'A'+1]=1;

127     }

128     for(i=1;i<=N;++i)

129         mat[0][i]=mat[N+1][i]=mat[i][0]=mat[i][N+1]=1;//给地图四周打上障碍

130     mat[1][1]=2;

131     printf("%d\n",max(Dfs(1,1,1),Dfs(1,1,2))+1);

132     return 0;

133 }