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 rounds, 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 value, 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 action (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 actions.

Shuai Shuai asks 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 one 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¹ + 2*2¹ = 6.

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

3rd round: The score is 3*2³ + 4*2³ = 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¹⁶.

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

Source

NOIP2007-S3