Weapon Engineering

Interview

Time limit2sMemory limit256 MB

Summary

On a grid of at most 5 by 5 cells, place L-shaped triominoes (with the corner counted twice) so the covered cells' score is maximized.

Level: Medium6 of 10
Topics: Backtracking, Brute force, Implementation, Matrix
Solved: No attempts yet

Problem

Gil-dong is an engineer developing a boomerang weapon that can protect his village from outside invasion. He obtained a high-grade piece of wood for making boomerangs. The wood is a rectangle of size NxM, and its strength differs slightly from one part to another.

For example, when the wood is 2x3, it consists of 6 cells as shown below.

Gil-dong wants to cut this wide rectangular piece of wood into several boomerangs. A boomerang always has the shape of a 'ㄱ' occupying 3 cells. Therefore there are 4 possible boomerang shapes, as shown below.

The center cell of a boomerang counts its strength twice. In the figure above, the cells colored yellow are the center cells. For example, in the earlier example, two boomerangs can be made as shown below, and the sum of their strengths is 46, which no other arrangement exceeds.

It is also fine to leave some positions of the wood unused. For example, in the earlier example, making only one boomerang as shown below is fine too. However, doing so gives a total strength of 18, which is inefficient.

Given the shape of the wood and the strength of each cell, write a program that outputs the maximum possible sum of the strengths of the boomerangs Gil-dong can make.

Input

The first line gives two positive integers N, M, the height and width of the wood Gil-dong has. (1 ≤ N, M ≤ 5) Each of the next N lines gives M positive integers K, the strength of each position of the wood, separated by spaces. (1 ≤ K ≤ 100)

Output

On the first line, print the maximum possible sum of the strengths of the boomerangs Gil-dong can make.

If the wood is too small to make even one boomerang, print 0.

Examples2

Example 1
Input
```
3 3
32 83 75
24 96 56
71 88 12
```
Expected output
```
632
```
Example 2
Input
```
1 1
7
```
Expected output
```
0
```