Abdullah and Haritha were building a 3D printed arcade machine. Abdullah had worked on the hardware, while Haritha had been working on the game that will be running on the arcade machine.

The game is represented as a 2D grid of R rows and C columns. The goal of the game is to build the maximum possible number of Hackatari logos. Hackatari‘s logo consists of 5 symbols, they are: {x,?o,??>?,??-?,?| }. When the game starts, the player will have an infinite number of the first two symbols {x,? and o}.

Each cell of the grid contains one of the three-to-last symbols of the logo, specifically, {?>?,??-?,? or | }.

The player is placed at the top-left cell, and is only allowed to move to the cell below him, or to the one to his right. The player is not allowed to go outside the grid. To collect a symbol from a cell, the player needs to move to that cell. The goal of the game is to build the maximum number of Hackatari logos using the collected symbols.

Abdullah was testing Haritha’s game, recently, and he got a score of 103%, which means that the maximum score that Haritha expected, was less than the maximum score that the player can actually achieve.

Can you help Haritha fix his game by writing a program that finds the maximum number of logos that can actually be built??

The first line of input contains two integers, R and C (1?≤?R,?C?≤?100), the number of rows and the number of columns in the grid, respectively.

Each of the following R lines contains C characters, each character belongs to the set: {?>?,??-?,?| }.

On a single line, print the maximum number of Hackatari logos.

3 4
>|>-
-|->
->-|

2

4 2
>-
>-
>-
||

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;
const int N = 1e2+10;
const int M = 1e6+10;
int n,m,k,tot=0,q;
bool dp[3][N][2*N][2*N];
char str[N][N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",str[i]+1);
    }
    dp[0][1][0][0]=true;
    for(int i=1;i<=n;i++){
        met(dp[(i+1)%3],0);
        for(int j=1;j<=m;j++){
            for(int x=0;x<=i+j-1;x++){
                for(int y=0;x+y<=i+j-1;y++){
                    if(dp[(i+2)%3][j][x][y]||dp[i%3][j-1][x][y]){
                        if(str[i][j]==‘>‘)dp[i%3][j][x+1][y]=true;
                        if(str[i][j]==‘|‘)dp[i%3][j][x][y+1]=true;
                        if(str[i][j]==‘-‘)dp[i%3][j][x][y]=true;
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<m+n;i++){
        for(int j=0;i+j<m+n;j++){
            if(dp[n%3][m][i][j]){
                int ret=min(i,min(j,m+n-1-i-j));
                ans=max(ret,ans);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}