Description

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的$n*m$的矩阵，矩阵中的每个元素$a_{ij}$据为非负整数。游戏规则如下： $1$. 每次取数时须从每行各取走一个元素，共$n$个。$m$次后取完矩阵所有的元素； $2$. 每次取走的各个元素只能是该元素所在行的行首或行尾； $3$. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值$*2i$，其中i表示第$i$次取数（从$1$开始编号）； $4$. 游戏结束总得分为$m$次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

Format

Input

输入包括$n+1$行； 第一行为两个用空格隔 开的整数$n$和$m$$（1\le n, m\le 80）$。 第$2n+1$行为$n*m$矩阵，其中每行有$m$个用单个空格隔开，$0\le a_{ij}\le 1000$。

Output

输出仅包含$1$行，为一个整数，即输入矩阵取数后的最大的分。

Samples

2 3
1 2 4
3 4 2

82

Hints

第$1$次：第一行取行首元素，第二行取行尾元素，本次得分为$1*2^1+2*2^1=6$ 第$2$次：两行均取行首元素，本次得分为$2*2^2+3*2^2=20$ 第$3$次：得分为$3*2^3+4*2^3=56$。总得分为$6+20+56=82$