Every morning at 8:30, the students
at LKSH gather for
morning exercises in front of the main building. Boys and girls stand on the
pavement, forming a rectangular grid.
On the
building's porch stands a photographer. He wants to take a group photo of some
boys and girls. To do this, he needs to select a rectangular area on the
pavement such that it contains an equal number of boys and girls. Unfortunately
for the students, there may be many such areas. The photographer wants to take
pictures of all these areas to choose the best one. Each photo takes one second
to take. Therefore, the students will continue their exercises for as many
seconds as there are suitable subrectangles!
Let's imagine
that a coordinate system is drawn on the pavement in front of the building.
Then the students stand at integer points, forming a rectangle of size h ? w with sides parallel to the coordinate axes. The
photographer needs to select a subrectangle with sides parallel to the axes.
Write a program
that calculates how many seconds the students will spend doing exercises.
Input. The first line contains
two natural numbers h and w (1 ≤ h, w ≤
300) – the dimensions of the rectangle formed by the students. Each of the
following h lines contains w numbers. A 0 indicates that a
boy is standing at that position, and a 1 indicates that a girl is
standing there.
Output. Print the number of
seconds the students will spend doing exercises.
|
Sample
input 1 |
Sample
output 1 |
|
3 4 0 1 0 0 1 0 1 1 0 0 0 1 |
20 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
3 1 0 0 0 |
0 |
dynamic
programming