시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 2 2 2 100.000%

문제

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. (1 ≤ N, M ≤ 750)

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.

예제 입력

3 3
011
110
100

예제 출력

6

예제 입력 2

5 5
10110
11111
11011
00100
11011

예제 출력 2

31

힌트

Sample 1

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

Sample 2

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