크기의 격자 보드가 주어진다.
보드는 개의 행과 개의 열로 이루어져 있으며, 각 칸에는 하나의 소문자 알파벳이 들어있다.
호반우는 다음과 같은 작업을 원하는 만큼 수행해 격자판에 숨어 있는 gori를 최대한 많이 찾고자 한다.
다음과 같은 작업을 원하는 만큼 수행할 수 있다고 한다.
gori예를 들어 위와 같은 격자판이 주어진 경우, 2행 2열부터 2행 5열까지 오른쪽 방향으로 연속한 개의 칸에 적힌 문자를 순서대로 이어붙이면 gori가 된다. 따라서 이 개의 칸을 선택해 점을 얻을 수 있다.
위 그림처럼 한 번의 작업에서 중간에 방향을 바꾸어 선택할 수 있다. 선택한 개의 칸은 반드시 상하좌우 방향으로 인접하게 연속해야 한다.
호반우가 얻을 수 있는 최대 점수를 구해보자.
첫 번째 줄에 행의 개수를 의미하는 과 열의 개수를 의미하는 이 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄에 결쳐 소문자 알파벳으로만 구성된 길이 의 문자열이 한 줄에 하나씩 주어진다.
호반우가 얻을 수 있는 최대 점수를 출력한다.