CCTV Control

Time limit2sMemory limit512 MB

Summary

Given an n by m grid of 1s and 2s that can be cyclically shifted in rows and columns, maximize the number of 2x2 blocks whose four cells all match.

Level: Hard8 of 10
Topics: Array, Implementation, Brute force, Math
Solved: No attempts yet

Problem

A security agency has won a contract to guard two buildings. Each building has many surveillance cameras installed.

One wall of the guard room is a rectangle made of $n$ horizontal rows with $m$ monitors in each row. Each monitor displays the feed from a camera located in one of the buildings. The guard room has an innovative control panel with four buttons: <>, <>, <>, and <>.

The <> button moves the image on every monitor to the monitor to its left. The image on the leftmost monitor in each row moves to the rightmost monitor of that row.

The <>, <>, and <> buttons work the same way. The <> button moves the image on every monitor to the monitor to its right. The image on the rightmost monitor in each row moves to the leftmost monitor of that row. The <> button moves the image on every monitor to the monitor above it. The images in the top row move to the monitors in the bottom row. The <> button moves the image on every monitor to the monitor below it. The images in the bottom row move to the monitors in the top row.

A $2 \times 2$ block of monitors is called convenient for observation if all of its monitors show feeds from the same building. Moving the images with the control panel can change the number of blocks convenient for observation. A single monitor may belong to several blocks convenient for observation.

Write a program that finds the maximum number of blocks convenient for observation that can be obtained by operating the monitors with the control panel.

Input

The first line contains two integers: $n$ , the number of rows, and $m$ , the number of monitors in each row. The next $n$ lines describe the rows of monitors from top to bottom. Each of these lines contains $m$ characters describing the monitors in that row from left to right. The character <<1>> means the monitor shows the feed from the first building, and the character <<2>> means the feed from the second building.

Output

Output a single integer: the maximum number of blocks convenient for observation that can be obtained by moving the images on the monitors.

Notes

In the first example, the <> command produces a block of 1s convenient for observation on the left and a block of 2s convenient for observation on the right.

In the second example, the monitors already contain two blocks convenient for observation.

In the third example, for instance, the <> and <> commands produce three blocks of 1s convenient for observation.

Examples3

Example 1
Input
```
2 4
1221
1221
```
Expected output
```
2
```
Example 2
Input
```
3 2
22
22
22
```
Expected output
```
2
```
Example 3
Input
```
3 3
111
121
111
```
Expected output
```
3
```