Description

Shuai Shuai often plays a matrix number-taking game with his classmates: Given an n*m matrix, each element a_ij in the matrix is a non-negative integer. The rules of the game are as follows:

1. Each time numbers are taken, one element must be taken from each row, totaling n elements. After m turns, all elements of the matrix will have been taken;

2. The elements taken each time can only be the first or last element of their respective rows;

3. Each number-taking action has a score, which is the sum of the scores for each row's number-taking. The score for taking a number from a row = the value of the taken element * 2ⁱ, where i represents the i-th number-taking turn (numbered starting from 1);

4. The total score at the end of the game is the sum of the scores from all m number-taking turns.

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

Input Format

The input consists of n+1 lines:

The first line contains two integers n and m, separated by a space.

Lines 2 to n+1 represent the n*m matrix, where each line contains m non-negative integers separated by single spaces.

Output Format

The output consists of a single line containing an integer, which is the maximum score obtained after taking all the numbers from the input matrix.

```input1 2 3 1 2 3 3 4 2 ``` ```output1 82 ``` ## Hint

【Sample Explanation】

1st round: Take the first element from the first row and the last element from the second row. The score for this round is 1*2^1 + 2*2^1 = 6

2nd round: Take the first element from both rows. The score for this round is 2*2^2 + 3*2^2 = 20

3rd round: The score is 3*2^3 + 4*2^3 = 56. The total score is 6 + 20 + 56 = 82

【Data Range】

60% of the data satisfies: 1 ≤ n, m ≤ 30, with the answer not exceeding 10^16

100% of the data satisfies: 1 ≤ n, m ≤ 80, 0 ≤ a_ij ≤ 1000

Source

NOIP2007-S3