题目背景

原题来自 NOIP 2007 提高组。

题目描述

帅帅经常和同学玩一个矩阵取数游戏。给定一个 $n \times m$ 的矩阵，矩阵中的每个元素 $a_{ij}$ 均为非负整数。

游戏规则如下：

1. 每次取数时，必须从每一行各取走一个元素，共取走 $n$ 个元素；
2. 每次取走的元素只能是该元素所在行的行首或行尾；
3. 一共进行 $m$ 次取数，最后取完矩阵中的所有元素；
4. 第 $i$ 次取数时，每行取数的得分为“被取走的元素值 $\times 2^i$”，本次得分为各行得分之和；
5. 游戏总得分为 $m$ 次取数得分之和。

请计算可以得到的最大总得分。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行包含 $m$ 个非负整数，表示矩阵中的元素。

输出格式

输出一行一个整数，表示最大总得分。

2 3
1 2 3
3 4 2

82

样例解释

第 $1$ 次：第 $1$ 行取行首 $1$，第 $2$ 行取行尾 $2$，得分为 $1 \times 2^1+2 \times 2^1=6$。

第 $2$ 次：两行均取行首，得分为 $2 \times 2^2+3 \times 2^2=20$。

第 $3$ 次：取剩余元素，得分为 $3 \times 2^3+4 \times 2^3=56$。

总得分为 $6+20+56=82$。

数据范围与提示

• 对于 $60\%$ 的数据，$1 \le n,m \le 30$，答案不超过 $10^{16}$
• 对于 $100\%$ 的数据，$1 \le n,m \le 80$，$0 \le a_{ij} \le 1000$

来源

NOIP 2007 提高组