#3748. 「一本通 5.1 练习 3」矩阵取数游戏 暂未评定

原题来自：NOIP 2007

帅帅经常和同学玩一个矩阵取数游戏：对于给定的 的矩阵，矩阵中每个元素 均为非负整数。游戏规则如下：

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

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

输入包括 行。 第一行两个空格隔开的正整数 接下来 行每行 个用空格隔开的整数。

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

样例输入 1

2 3
1 2 3
3 4 2

样例输出 1

82

样例解释 1

第一次：第一行取行首元素，第二行取行尾元素，本次得分为 ；
第二次：两行均取行首元素，本次得分为 ；
第三次：本次得分为 ，总得分为 。

样例输入 2

1 4
4 5 0 5

样例输出 2

122

样例输入 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

对于 的数据，，答案不超过 ；
对于 的数据，。