Description

Original Source: NOIP 2007

Shuai Shuai often plays a matrix number game with his classmates: Given an $n\times m$ matrix where each element $a_{ij}$ is a non-negative integer, the game rules are as follows:

1. Each time numbers are taken, one element must be taken from each row, totaling $n$ elements. All elements are taken after $m$ rounds.
2. The elements taken each time must be either the first or the last element of their respective rows.
3. Each round of taking numbers has a score, which is the sum of the scores from each row. The score for taking a number from a row is calculated as the taken element value $\times 2^i$, where $i$ represents the $i$-th round of taking numbers, starting from 1.
4. At the end of the game, the total score is the sum of the scores from all $m$ rounds.

Shuai Shuai asks you to write a program that, for any given matrix, can compute the maximum possible score after taking all the numbers.

Input Format

The input consists of $n+1$ lines. The first line contains two space-separated positive integers $n$ and $m$. The next $n$ lines each contain $m$ space-separated integers.

Output Format

Output a single integer, which is the maximum score obtainable from the input matrix after taking all the numbers.

Sample 1

First round: Take the first element from the first row and the last element from the second row. The score for this round is $1\times 2^1 + 2\times 2^1 = 6$. Second round: Take the first element from both rows. The score for this round is $2\times 2^2 + 3\times 2^2 = 20$. Third round: The score for this round is $3\times 2^3 + 4\times 2^3 = 56$. The total score is $6 + 20 + 56 = 82$.

2 3
1 2 3
3 4 2

82

Sample 2

1 4
4 5 0 5

122

Sample 3

2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67

316994

Data Range and Hint

For $60\%$ of the data, $1\le n,m\le 30$, and the answer does not exceed $10^{16}$;
For $100\%$ of the data, $1\le n,m\le 80$, and $0\le a_{i,j}\le 1000$.