原題來(lái)自：NOIP 2007

帥帥經(jīng)常和同學(xué)玩一個(gè)矩陣取數(shù)游戲：對(duì)于給定的 n×m 的矩陣，矩陣中每個(gè)元素 a_ij 均為非負(fù)整數(shù)。游戲規(guī)則如下：

1、每次取數(shù)時(shí)必須從每行各取走一個(gè)元素，共 n 個(gè)，m 次取完所有元素。

2、每次取走的各個(gè)元素只能是該元素所在行行首或行尾。

3、每次取數(shù)都有一個(gè)的分值，為每行取數(shù)得分之和，每行取數(shù)得分==被取走元素值×2ⁱ ，其中 i 表示第 i 次取數(shù)，從 1 開始計(jì)數(shù)。

4、游戲結(jié)束時(shí)，總得分為 m 次取數(shù)得分之和。

帥帥想讓你幫忙寫一個(gè)程序，對(duì)于任意矩陣，可以求出取數(shù)后的最大得分。

輸入包括 n+1 行。 第一行兩個(gè)空格隔開的正整數(shù) n,m 接下來(lái) n 行每行 m 個(gè)用空格隔開的整數(shù)。

樣例解釋 1

第一次：第一行取行首元素，第二行取行尾元素，本次得分為 1×2¹+2×2¹=6；

第二次：兩行均取行首元素，本次得分為 2×2²+3×2²=20；

第三次：本次得分為 3×2³+4×2³=56，總得分為 6+20+56=82。

數(shù)據(jù)范圍與提示：

對(duì)于 60% 的數(shù)據(jù)，1≤n,m≤30，答案不超過(guò) 10¹⁶ ；

對(duì)于 100% 的數(shù)據(jù)，1≤n,m≤80,0≤a_i,j≤1000。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃