一只退役蒟蒻 @ 2020-08-26 09:48:43
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define lowbit(x) (x&-x)
#define LL long long
using namespace std;
int read()
{
int s=0,bj=0;
char ch=getchar();
while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return bj?-s:s;
}
void printnum(int x)
{
if(x>9)printnum(x/10);
putchar(x%10^48);
}
void print(int x,char ch)
{
if(x<0){putchar('-');x=-x;}
printnum(x);putchar(ch);
}
int n,m,f[1<<10][1<<10][3];//no lst
int a[15],sum[71],bj[71],cnt,ans;char ch[15];
int Sum(int x)
{
int num=0;
while(x){x-=lowbit(x);++num;}
return num;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)
{
scanf("%s",ch);
for(int j=0;j<m;++j)
{
a[i]<<=1;
a[i]+=ch[j]=='H';
}
}
for(int i=0;i<(1<<m);++i)if(!(i&(i<<1)||(i&(i<<2)))){sum[++cnt]=Sum(i);bj[cnt]=i;}
// for(int i=1;i<=cnt;++i)if(!(bj[i]&a[1]))f[i][0][1]=sum[i];
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j)
{
if(bj[i]&bj[j]||bj[i]&a[2]||bj[j]&a[1])continue;
f[i][j][2]=sum[i]+sum[j];//i,j,2
}
for(int i=3;i<=n;++i)
for(int j=1;j<=cnt;++j)//no
{
if(bj[j]&a[i])continue;
for(int k=1;k<=cnt;++k)
{
if((bj[k]&a[i-1])||(bj[j]&bj[k]))continue;//lst
for(int l=1;l<=cnt;++l)//lst2
{
if((bj[l]&bj[k])||(bj[l]&bj[j])||(bj[l]&a[i-2]))continue;
f[j][k][i%3]=max(f[j][k][i%3],f[k][l][(i-1)%3]+sum[j]);
}
}
}
for(int i=1;i<=cnt;++i)
for(int j=1;j<=cnt;++j)ans=max(ans,f[i][j][n%3]);
print(ans,'\n');
return 0;
}