Crush Fever

Interview

Time limit1.5sMemory limit512 MB

Summary

On an N by M grid of 5 piece kinds, choose 3 taps; each tap clears the connected same-kind group of the tapped cell and scores size squared, with pieces falling down after each tap. Maximize total points.

Level: Medium6 of 10
Topics: DFS, Brute force, Implementation, Simulation
Solved: No attempts yet

Problem

Junseo plays games on every platform there is, and he found one called Crush Fever on a mobile app store. You raise units, build a party, and run dungeons, but every battle is fought as a puzzle. After failing to clear a dungeon by hand, he decided to write a program that plays for him. He is writing the part that taps the screen himself, and he handed you the part that scores well on the puzzle.

There are 5 kinds of puzzle pieces. They are not scattered the way the picture above shows; they sit in a grid. On your turn you tap pieces three times. One tap destroys the piece you tapped, and every piece of the same kind joined to it up, down, left, or right is destroyed with it. The destruction follows the connections, so a single tap clears one whole connected group of a single kind. Destroying $P$ pieces at once earns $P^2$ points. After that, the pieces left hanging in the air sink down their own column and fill the empty cells.

For example, tapping one piece of the group of 3s shaded yellow below

leaves this.

Find the highest score Junseo can earn in one turn. Once the grid is empty, the remaining taps cannot be used.

Input

The program reads from standard input. The first line has the width $M$ and the height $N$ of the puzzle, separated by a space. ( $1 \le M, N \le 8$ )

Each of the next $N$ lines has $M$ integers $c$ separated by spaces, the kinds of the pieces in that row. ( $1 \le c \le 5$ ) The first of those lines is the top row of the grid and the last one is the bottom row. Every cell holds one piece at the start.

Output

The program writes to standard output. Print on one line the highest score Junseo can earn in one turn.

Examples2

Example 1

Input

6 3
1 1 1 1 1 1
1 1 1 2 2 2
2 2 2 3 3 3

Expected output

Example 2
Input
```
2 3
1 2
1 2
2 1
```
Expected output
```
14
```