양손에 V

시간 제한2초메모리 제한1024 MB

요약

흰색과 검은색 격자로 이루어진 판에서 흰색 격자 두 개를 골라 각각 왼쪽 위와 오른쪽 위 대각선으로 이어지는 V자를 칠할 때, 파란색이 되는 격자 수의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 누적 합, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

각 격자가 흰색 또는 검은색으로 칠해져 있는 $N$ 행 $M$ 열의 격자판이 주어진다.

다음과 같은 행동을 "V자 색칠하기" 라 하자:

흰색 격자를 하나 선택한다.
선택한 격자부터 시작하여 왼쪽 위 대각선을 따라 움직이면서 흰색이 아닌 격자가 나오거나 외부로 빠져나가기 전까지의 격자들을 모두 파란색으로 칠한다.
선택한 격자의 한 칸 오른쪽 위 격자부터 시작하여 오른쪽 위 대각선을 따라 움직이면서 흰색이 아닌 격자가 나오거나 외부로 빠져나가기 전까지의 격자들을 모두 파란색으로 칠한다.

"V자 색칠하기"를 두 번 했을 때 가능한 파란색 격자의 최대 개수를 구하여라.

예를 들어, 다음과 같은 격자판이 주어졌다 하자.

5행 5열의 격자에서 V자 색칠하기를 한 후 격자판의 상태는 다음과 같다.

그 후, 5행 9열의 격자에서 V자 색칠하기를 하면 다음과 같이 총 11개의 격자가 파란색으로 칠해진다.

반면, 5행 9열의 격자에서 먼저 V자 색칠하기를 한 후 5행 5열의 격자에서 V자 색칠하기를 하면 다음과 같이 총 13개의 격자가 파란색으로 칠해진다.

두 번의 V자 색칠하기로 13개보다 많은 격자를 파란색으로 칠하는 방법은 존재하지 않으므로, 주어진 격자판에서의 답은 13이 된다.

입력

첫 번째 줄에 $N$ 과 $M$ 이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$ 개의 줄에 걸쳐 격자판에 대한 정보가 주어진다. 각 줄에는 $0$ 또는 $1$ 로 이루어진 길이 $M$ 인 문자열이 주어진다. $N$ 개의 줄 중 $i$ 번째 줄의 $j$ 번째 문자가 $1$ 이면 격자판에서 $i$ 행 $j$ 열의 격자가 흰색, $0$ 이면 검은색임을 뜻한다. ( $1 \le i \le N, 1 \le j \le M$ )

출력

첫 번째 줄에 가능한 파란색 격자의 최대 개수를 출력한다.

제한

$1 \le N, M \le 3\\,000$
주어지는 격자판에서 흰색 격자는 최소 2개 존재한다.

예제2

예제 1

입력

5 11
10001000000
01000100000
00100110001
00010101010
00001000100

예상 출력

예제 2
입력
```
3 3
111
111
111
```
예상 출력
```
6
```