#2043. 矩阵取数游戏

矩阵取数游戏

Description



题描述
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的nXm的矩阵,矩阵中的每个元素a均
为非负整数。游戏规则如下
①每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有的元素
②每次取走的各个元素只能是该元素所在行的行首或行尾;
2、③每次取数都有一个得分值,为每行取数的得分之和;每行取数的得分=被取走的元素值*(2^i)
其中i表示第i次取数(从1开始编号)
④游戏结東总得分为m次取数得分之和
帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。

Input Format

输入文件包括n+1行

第一行为两个用空格隔开的整数n和m

第2-n+1行为N*M矩阵,其中每行m个用单个空格隔开

Output Format

输出文件仅包含一行,为一个整数,即输入矩阵去数后的最大得分
2 3
1 2 3
3 4 2
82

Hint

60%的数据满足:1<=n, m<=30,答案不超过10^16

100%的数据满足:1<=n, m<=80,0<=aij<=1000

Source

动态规划