Two Hands, One V

Time limit2sMemory limit1024 MB

Summary

Given a binary grid, find the maximum number of blue cells after two V-shaped paintings, each following an upper-left and upper-right diagonal from a white cell.

Level: Medium6 of 10
Topics: Matrix, Dynamic programming, Implementation
Solved: No attempts yet

Problem

Each cell of an $N$ -row, $M$ -column grid is painted either white or black.

An action called "V-shaped painting" is defined as follows:

Choose one white cell.
Starting from the chosen cell, move along the upper-left diagonal and paint every cell you pass blue, until you reach a cell that is not white or leave the grid.
Starting from the cell one step to the upper right of the chosen cell, move along the upper-right diagonal and paint every cell you pass blue, until you reach a cell that is not white or leave the grid.

Find the maximum number of blue cells possible after performing "V-shaped painting" twice.

For example, suppose the following grid is given.

After one V-shaped painting at row 5, column 5, the grid looks like this.

Then a V-shaped painting at row 5, column 9 paints 11 cells blue in total.

By contrast, a V-shaped painting at row 5, column 9 followed by one at row 5, column 5 paints 13 cells blue in total.

No two V-shaped paintings can color more than 13 cells blue, so the answer for this grid is 13.

Input

The first line contains $N$ and $M$ , separated by a space.

The next $N$ lines describe the grid. Each line is a string of length $M$ made of $0$ and $1$ . If the $j$ -th character of the $i$ -th line is $1$ , the cell at row $i$ , column $j$ is white. If it is $0$ , the cell is black. ( $1 \le i \le N, 1 \le j \le M$ )

Output

Print the maximum number of blue cells that can be obtained on the first line.

Constraints

$1 \le N, M \le 3\,000$
The grid contains at least 2 white cells.

Examples2

Example 1

Input

5 11
10001000000
01000100000
00100110001
00010101010
00001000100

Expected output

Example 2
Input
```
3 3
111
111
111
```
Expected output
```
6
```