Skip to content

P1005 [NOIP 2007 Advanced Group] Matrix Number Game

Description

Shuai Shuai often plays a matrix number game with his classmates:
For a given \(n \times m\) matrix, each element \(a_{i,j}\) is a non-negative integer.
The rules of the game are as follows:

  1. In each turn, exactly one element must be taken from each row, for a total of \(n\) elements. After \(m\) turns, all elements in the matrix will have been taken;
  2. The element taken from each row must be either the first or the last element of that row;
  3. Each turn yields a score, which is the sum of the scores from each row. The score for a row is defined as the value of the chosen element \(\times 2^i\), where \(i\) is the index of the turn (starting from \(1\));
  4. The total score of the game is the sum of the scores from all \(m\) turns.

Shuai Shuai wants you to write a program that, for any matrix, computes the maximum possible score.

Input

The input consists of \(n+1\) lines:

  • The first line contains two integers \(n\) and \(m\), separated by a space.
  • The next \(n\) lines each contain \(m\) non-negative integers, representing the \(n \times m\) matrix.

Output

Output a single integer: the maximum possible score after taking numbers from the matrix.

Sample #1

2 3
1 2 3
3 4 2

82

Note / Hint

[Data Range]

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\), \(0 \le a_{i,j} \le 1000\).

[Source]
NOIP 2007 Advanced Group, Problem 3.