Collecting samples

Assignment

A team of NASA researches aims to collect mineral samples from a surface of a distant planet. An exploration rover will be deployed for this task. To plan its movement, the area of interest is divided into sectors forming a regular rectangular grid. Three types of sectors are distinguished: rich in minerals, toxic and neutral. The researches look for an optimal route, which will take the rover through a maximal possible number of rich in minerals sectors. This task is not trivial as the environment on the surface and the technical parameters of the rover pose significant restrictions on the movement. The starting sector, where the rover is dropped, can be chosen arbitrarily. From the starting sector, the rover has to move eastwards (through next K > 0 sectors), southwards (again through next K sectors), westwards (K sectors) and northwards (K sectors), returning to the initial position. This means that the rover makes a loop around the perimeter of a square and visits 4_K_ sectors. The samples, which were collected in the rich sectors, can degrade and become useless if the rover moves through many toxic sectors. The researches calculated that this degradation does not occur if and only if the number T of toxic sectors visited by the rover is at most half the number R of visited rich in minerals sectors (i.e., T ≤ R / 2).

Image 1. Sectors map examples. Rich in minerals sectors are green, toxic sectors are violet and neutral sectors are white. Optimal routes are depicted by the red arrows.

The task

You are given a map of sectors. Your task is to compute the maximal number of rich in minerals sectors that can be visited by the rover when its movement is limited by the above formulated restrictions.

Input

The first input line contains two integers M and N determining the sectors grid size: M is the number of rows, N is the number of columns. Next, there are M lines, each of them containing N integers, separated by a space, describing types of sectors in the row. Each neutral sector is represented by value 0, rich in minerals sector is represented by value 1 and toxic sector is represented by value 2. It holds M ≥ 2, N ≥ 2 and MN ≤ 10⁶.

Output

The output consists of one line containing one non-negative integer which equals the maximal number of rich in minerals sectors visited by the rover following the given rules and keeping the collected samples nondegraded.

Examples

Example 1

Input

Output

The solution of Example 1 is visualized in Image 1a).

Example 2

Input

6 8
0 0 2 2 2 1 2 1
0 1 2 2 1 0 1 1
0 0 1 0 1 2 0 2
2 1 0 2 2 1 1 1
1 2 1 0 0 0 1 0
1 2 0 1 1 2 1 1

Output

The solution of Example 2 is visualized in Image 1b).

Example 3

Input

8 10
1 2 0 0 2 0 2 2 1 2
2 1 2 2 1 1 2 1 2 2
1 2 1 1 1 0 2 2 2 1
0 2 2 1 0 2 2 2 1 2
2 2 2 1 0 2 1 2 2 0
1 0 1 1 2 0 2 1 1 1
2 2 0 2 2 0 1 2 2 0
0 2 2 0 2 2 0 2 0 2

Output

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Veřejná data