该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

To the greatest All-around King zsp！

题目描述

伟大的查重专家zsp正在find gpt.

In a contest,it's not good to ask gpt for help.

给出 $n$ 行 $m$ 列的矩阵 $s$，矩阵中每个格子都有一个字母,字母取值范围为 $\{g,p,t\}$。$s_{i,j}$表示第 $i$ 行第 $j$ 列的格子中的字母。定义矩阵中一条特殊路径形成如下：

1. 选中一个点 $(i,j)$ 作为起点，记此时坐标为 $(u,v)$。 接下来执行操作2或操作3。

2. 选择移动至坐标为 $(u+1,v)$（要求 $u+1 \leq n$）或者$(u,v+1)$（要求 $v+1\leq m$）的格子。然后选择执行操作2或操作3。

3. 退出过程。

对于一条特殊路径，连接从头至尾经过格子中的字符，能得到一个字符串，定义这个字符串的价值为这个字符串含有多少个子串为 gpt。于是zsp想问所有特殊路径所能形成的字符串的最大价值。

子串定义：若字符串 $a$ 能由字符串 $b$ 左边连续删 $0$ 或以上个字符且右边连续删 $0$ 或以上个字符得到，则称 $a$ 为 $b$ 的子串。例如对于字符串 abcdef, ab、c、def是其子串，而acd、df不是其子串。

输入格式

第一行两个整数n,m,表示矩阵的行数列数。($1\leq n,m \leq1000$ )

接下来n行，每行m个字母，表示矩阵中的字母。对每个字母x，有$x \in \{g,p,t\}$,保证字母小写。

输出格式

输出一个整数，表示能得到的字符串的最大价值。

样例 #1

样例输入 #1

2 2
gp
pt

样例输出 #1

1

样例 #2

样例输入 #2

1 6
gptgpt

样例输出 #2

2

样例 #3

样例输入 #3

2 2
gp
gp

样例输出 #3

0

提示

对样例一，从 $(1,1)$ 处出发长度为 $3$ 的路径有两条

一条是 $(1,1)->(1,2)->(2,2)$ ,形成的字符串为 gpt,价值为 $1$

另一条是 $(1,1)->(2,1)->(2,2)$,形成的字符串为 gpt,价值为 $1$

对样例二，最大价值的字符串为 gptgpt，该字符串中 gpt 共出现了两次，故价值为 $2$