Parcel

Time limit3sMemory limit512 MB

Summary

Given an n by n grid of 0 (arable) and 1 (waste), find the largest all-zero rectangle and print its area. n can be up to 2000.

Level: Medium7 of 10
Topics: Stack, Dynamic programming, Matrix, Prefix sum
Solved: No attempts yet

Problem

We are given a square field. The field has a side of length $n$ and is divided into $n^2$ unit squares of side $1$ . Each square is either arable land or waste land.

We want to delimit a parcel in the field. The parcel must be a rectangle and must consist only of arable squares. The area of the parcel equals the area of the corresponding rectangle. We look for a parcel of the largest possible area.

Write a program that:

reads the description of the field from standard input,
computes the area of the largest parcel (there may be more than one such parcel),
writes the computed area to standard output.

Input

The first line contains one integer $n$ ( $1 \le n \le 2000$ ).

Each of the next $n$ lines describes one row of the field. Each line contains $n$ numbers, each $0$ or $1$ , separated by single spaces. The numbers describe the squares of the row in order: $0$ denotes an arable square and $1$ denotes a waste square.

Output

Print a single integer on one line: the area of the largest parcel. If every square is waste land and no parcel exists, print $0$ .

Examples2

Example 1

Input

Expected output

Example 2
Input
```
4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
```
Expected output
```
16
```