Description

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

1. In each round, exactly one element is taken from each row, for a total of $n$ elements. After $m$ rounds, all elements in the matrix are taken.
2. Each taken element must be either the leftmost or the rightmost element of its row.
3. The score of each round is the sum of the per-row scores. The per-row score equals the value of the taken element $\times 2^i$, where $i$ denotes the $i$-th round (starting from $1$).
4. The total score of the game is the sum of the scores over all $m$ rounds.

Please write a program that, for any given matrix, computes the maximum possible total score.

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$ contain the $n \times m$ matrix. Each line has $m$ non-negative integers separated by single spaces.

Output Format

Output a single line containing one integer: the maximum possible total score.

2 3
1 2 3
3 4 2

82

Hint

• Constraints:
  • For $60\%$ of the testdata, $1 \le n, m \le 30$, and the answer does not exceed $10^{16}$.
  • For $100\%$ of the testdata, $1 \le n, m \le 80$, $0 \le a_{i,j} \le 1000$.
• Source: NOIP 2007 Senior, Problem 3.

Translated by ChatGPT 5