Counting Empty Parallelograms in a Diamond Grid

A large diamond of side length n is uniformly subdivided into a grid of n × n small diamonds (each with side length 1) by two families of parallel lines. Originally every small diamond is separated by grid lines. However, some of these edges have been erased. Your task is to count the number of parallelograms (whose sides are segments of the remaining grid lines) that lie entirely within the large diamond and do not contain any interior edge (i.e. no grid line exists strictly inside the parallelogram).

A parallelogram in this grid is defined by choosing two distinct lines from the first family (which we call the "/" family) and two distinct lines from the second family (the "\" family). In the complete grid, the "/" family is described by n+1 lines, each divided into n segments, and similarly for the "\" family. The boundaries of a chosen parallelogram are these 4 lines; however, the interior of the parallelogram might contain segments if they have not been erased. Formally, if you choose two "/" boundaries with indices r1 and r2 (with 0 ≤ r1 < r2 ≤ n) and two "\" boundaries with indices d1 and d2 (with 0 ≤ d1

• All segments on the "/" lines in rows r where r1 < r < r2 and in columns from d1 to d2-1.
• All segments on the "\" lines in rows r where d1 < r < d2 and in columns from r1 to r2-1.

This parallelogram is empty if and only if every such segment in its interior has been erased (i.e. its value is 0). Note that if there is no interior (for example, when the chosen boundaries are consecutive), the parallelogram is considered empty.

The input provides the state of the grid edges as follows:

• An integer n representing the side length of the large diamond.
• Followed by n+1 lines, each containing n integers (either 0 or 1) representing the status of the / edges. A value of 1 means the edge is present and 0 means it has been erased.
• Then, another n+1 lines follow, each with n integers representing the status of the \ edges in the same format.

Your program should output the count of empty parallelograms that can be formed.

Note: In the above, indices for the edge arrays range as follows:

• The / edge matrix has dimensions (n+1) × n, where the row index goes from 0 to n and the column index from 0 to n-1.
• The \ edge matrix has the same dimensions.

A candidate parallelogram selected by boundaries (r1, r2) from the / family and (d1, d2) from the \ family is valid if: $$\forall r,\; r1 < r < r2,\; \forall j,\; d1 \le j \le d2-1: \; /_{r}[j]=0 $$

and

$$\forall r,\; d1 < r < d2,\; \forall j,\; r1 \le j \le r2-1: \; \\_{r}[j]=0. $$

inputFormat

The input begins with an integer n (1 ≤ n ≤ a small number) on a single line. This is followed by n+1 lines each containing n space-separated integers (each either 0 or 1) representing the / edge matrix. After that, there are n+1 lines each with n space-separated integers representing the \ edge matrix.

outputFormat

Output a single integer: the number of empty parallelograms in the grid.

sample

1
1
1
1
1

1