题目描述

强哥最近沉迷一款名为《矩阵抽卡王》的手游。游戏中有 $n$ 个卡池，每个卡池里有 $m$ 张排成一列的珍贵卡牌，每张卡牌都有一个战力值 $a_{ij}$。

游戏规则如下：

1. 每次抽卡必须从每个卡池各抽一张，共抽 $n$ 张，总共抽 $m$ 轮抽完所有卡牌。
2. 每次抽卡时，只能选择卡池最左边或最右边的那张卡牌。
3. 每轮抽卡的得分为所有抽中卡牌的战力值之和乘以 $2^i$，其中 $i$ 是当前轮次（从1开始）。
4. 游戏总得分为所有轮次得分的总和。

强哥想成为服务器第一，需要计算最大可能获得的总得分。你能帮他写个程序吗？

输入格式

第一行两个正整数 $n$ 和 $m$，表示卡池数量和每个卡池的卡牌数。 接下来 $n$ 行，每行 $m$ 个非负整数，表示每个卡池中卡牌的战力值。

输出格式

输出一个整数，表示强哥能获得的最大总得分。

样例

输入样例1

1 4  
4 5 0 5

输出样例1

122

输入样例2

2 10  
96 56 54 46 86 12 23 88 80 43  
16 95 18 29 30 53 88 83 64 67

输出样例2

316994

数据范围

• $1 \leq n, m \leq 30$
• 答案不超过 $10^{16}$
• 所有卡牌战力值为非负整数