Paper Folding

Time limit2sMemory limit128 MB

Summary

Given an N by M grid of integers, repeatedly fold it along row or column lines so overlapping cells sum, and find the maximum value obtainable in any cell.

Level: Hard8 of 10
Topics: Dynamic programming, Intervals, Combinatorics, Simulation
Solved: No attempts yet

Problem

You are given a rectangular sheet of paper divided into (N) rows and (M) columns of 1×1 cells. Each cell contains one integer.

You may fold the paper any number of times. In one fold, choose a line between two adjacent rows or between two adjacent columns, then fold one side onto the other. After a fold, if several cells overlap at the same position, the value at that position is the sum of the values written in those cells.

Considering every possible way to fold the paper, find the maximum value that can appear in any cell of the folded paper.

Input

The first line contains the height (N) and width (M) of the paper. Both (N) and (M) are positive integers no greater than 12.

The next (N) lines each contain (M) integers, the values written in the cells. The absolute value of each integer is at most 100.

Output

Print one integer: the maximum value that can appear in a cell.

Examples5

Example 1

Input

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

Expected output

Example 2
Input
```
2 3
1 1 1
1 1 1
```
Expected output
```
6
```
Example 3
Input
```
2 2
1 -1
1 -1
```
Expected output
```
2
```
Example 4
Input
```
1 1
0
```
Expected output
```
0
```

Example 5

Input

3 4
20 13 -2 100
-12 0 4 -3
4 1 -36 21

Expected output