题目描述

上语文课的时候，小 $C$ 的老师看着大家都无精打采，死气沉沉的，为了活跃课堂的气氛，老师决定让大家一起玩个游戏，老师听说体育课的时候大家一起玩了一个“硬币游戏”，于是也决定玩这个，可是老师又不想和体育课的那个游戏一模一样，不然就太没意思了，于是修改了游戏规则。

现在教室里同学的座位是一个 $n\times m$ 的矩阵，给每个同学发 $a_{i,j}$ 个硬币，”挑战者“进行选人拿硬币(”挑战者“离开座位的时候，老师会到“挑战者”的座位，不会存在空位)，现在拿硬币的规则如下：

1. 每次拿硬币时须从每行拿走一个硬币，共 $n$ 个。$m$ 次后拿走所有同学的硬币；

2. 每次拿走的硬币只能是行首或者行尾的硬币(每一行有硬币的第一个同学或者有硬币的最后一个同学)；

3. 每次拿硬币都有一个得分值，为每行拿硬币的得分之和，每行取数的得分 = 被拿走的硬币个数 $\times$ $2^i$ ,其中 $i$ 表示第 $i$ 次拿硬币(从 $i$ 开始编号)；

4. 游戏结束总分为 $m$ 次拿硬币得分之和。

小$C$想让你帮忙写一个程序，对于任意的矩阵，可以求出拿硬币后的最大得分。

输入格式

第$1$行为两个用空格隔开的整数 $n$ 和 $m$。$(1\leq n,m \leq 80)$ 接下来的 $n$ 行每行 $m$ 个整数，表示队伍中每个同学手上的硬币数 $a_{i,j}$。$(0 \leq a_{i,j} \leq 1000)$

输出格式

输出一个整数，即拿硬币之后的最大得分。

样例#1

输入样例#1

2 3
1 2 3
3 4 2

输出样例#1

82

样例#2

输入样例#2

1 4
4 5 0 5

输出样例#2

122

样例#3

输入样例#3

2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67

输出样例#3

316994

提示说明

对于第一组数据：

第 $1$ 次：第 $1$ 行取行首元素，第 $2$ 行取行尾元素，本次得分为 $1 \times 21 + 2 \times 21 = 6$，

第 $2$ 次：两行均取行首元素，本次得分为 $2 * 22 + 3 * 22 = 20$，

第 $3$ 次：得分为 $3 \times 23 + 4 \times 23 = 56$。

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