시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 32 MB188746.667%

문제

Humans finally landed on one of the Centaurus Constellation planets. A big surprise (or not!): the planet is inhabited by monsters! The monsters’ defense system is composed of battle cells, arranged in the form of a matrix with N rows and M columns.

Our intergalactic army has already attacked some of the cells, but now it is your turn to destroy exactly one cell.

By definition, the strength of the monsters’ defense system is equal to the number of submatrices (possibly overlapping) that contain only intact cells.A submatrix is a nonempty matrix obtained from the original matrix by eventually removing:

  • Some consecutive rows, starting from the first one;
  • Some consecutive rows, ending at the last one;
  • Some consecutive columns, starting from the first one;
  • Some consecutive columns, ending at the last one.

Select a cell to be destroyed by you in a way that minimizes the strength of the defense system.

Develop a program to calculate the strength of the defense system after your attack.

입력

The first line of the standard input contains two space separated integers N and M representing the number of rows, and the number of columns, respectively.

Each of the next N lines contains a binary string of size M, representing the cells of the matrix. A 1 corresponds to an intact cell, while a 0 corresponds to a cell already destroyed by our army.

There is at least one intact cell in the defense system.

출력

Write on the single line of the standard output the strength of the defense system after your attack.

제한

  • There is at least one intact cell in the defense system.

서브태스크

번호 배점 제한
1 12

1 ≤ N, M ≤ 50.

2 16

1 ≤ N, M ≤ 200.

3 27

1 ≤ N, M ≤ 500.

4 45

1 ≤ N, M ≤ 750.

예제 입력 1

3 3
011
110
100

예제 출력 1

6

The initial strength of the monsters’ defense system is 9. By destroying the intact cell on the intersection of the 2nd row and 2 nd column, the defense system will be of strength 6 and will look as follows:

011
100
100

예제 입력 2

5 5
10110
11111
11011
00100
11011

예제 출력 2

31

The initial strength of the monsters’ defense system is 44. By destroying the intact cell on the intersection of the 2nd row and 4th column, the defense system will be of strength 31 and will look as follows:

10110
11101
11011
00100
11011

채점 및 기타 정보

  • 예제는 채점하지 않는다.