#500. 矩阵取数游戏

矩阵取数游戏

题目描述

原题来自:NOIP 2007

帅帅经常和同学玩一个矩阵取数游戏:对于给定的 n×mn\times m 的矩阵,矩阵中每个元素 aija_{ij} 均为非负整数。游戏规则如下:

  1. 每次取数时必须从每行各取走一个元素,共 nn 个,mm 次取完所有元素。
  2. 每次取走的各个元素只能是该元素所在行行首或行尾。
  3. 每次取数都有一个的分值,为每行取数得分之和,每行取数得分==被取走元素值×2i\times 2^i,其中 ii 表示第 ii 次取数,从 11 开始计数。
  4. 游戏结束时,总得分为 mm 次取数得分之和。

帅帅想让你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

输入格式

输入包括 n+1n+1 行。 第一行两个空格隔开的正整数 n,mn,m 接下来 nn 行每行 mm 个用空格隔开的整数。

输出格式

输出为一个整数,为所输入矩阵取数后的最大得分

样例 1

2 3
1 2 3
3 4 2
82

第一次:第一行取行首元素,第二行取行尾元素,本次得分为 1×21+2×21=61\times 2^1+2\times 2^1=6; 第二次:两行均取行首元素,本次得分为 2×22+3×22=202\times 2^2+3\times 2^2=20; 第三次:本次得分为 3×23+4×23=563\times 2^3+4\times 2^3=56,总得分为 6+20+56=826+20+56=82

1 4
4 5 0 5
122
2 10
96 56 54 46 86 12 23 88 80 43
16 95 18 29 30 53 88 83 64 67
316994

数据范围与提示

对于 60%60\% 的数据,1n,m301\le n,m\le 30,答案不超过 101610^{16}
对于 100%100\% 的数据,1n,m80,0ai,j10001\le n,m\le 80,0\le a_{i,j}\le 1000