Photography#5236
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 \times 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.
The first line contains two natural numbers and w~(1 \le h, w \le 300) — the dimensions of the rectangle formed by the students. Each of the following lines contains numbers. A indicates that a boy is standing at that position, and a indicates that a girl is standing there.
Print the number of seconds the students will spend doing exercises.
Esempio 1
Esempio 2