Paper folding 2

Time limit1sMemory limit128 MB

Summary

Fold a 6 by 6 or smaller number grid along grid lines so overlapping cells add up, and maximize the value held in one cell.

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

Problem

You have a rectangular sheet of paper. The sheet is divided into $1 \times 1$ cells, and each cell holds one integer.

You fold the sheet along a straight line that runs between two rows or between two columns. A fold lays one side of the sheet on top of the other, and where two cells come to overlap, the number in that place becomes the sum of the two numbers. A part that already consists of several layers folds as one piece, with every layer moving together. A cell that reaches past the other side and overlaps nothing keeps its own number. There is no limit on how many times you fold, and folding zero times is allowed.

Write a program that finds the largest number a single cell can hold after you fold the sheet however you want.

Input

The first line contains the height $N$ and the width $M$ of the sheet. $N$ and $M$ are natural numbers at most $6$ . Each of the next $N$ lines contains $M$ integers, the numbers written in that row. Every one of those numbers has absolute value at most $100$ .

Output

Print the largest number a single cell can hold.

Examples1

Example 1

Input

4 4
1 -1 -1 1
-1 -1 -1 -1
-1 -1 -1 -1
1 -1 -1 1

Expected output