题目描述

小明和小红在玩一个矩阵取数游戏。给定一个 $n \times m$ 的矩阵，每个元素 $a_{i,j}$ 都是非负整数。游戏规则如下：

1. 每一轮必须从每一行各取走一个元素，共取 $m$ 轮，取完矩阵中所有元素。
2. 每轮取走的元素只能是该行当前剩余元素的最左端或最右端。
3. 每轮的得分为所有行取走元素值之和乘以 $2^i$，其中 $i$ 是轮次编号（从 $1$ 开始）。
4. 游戏总得分为 $m$ 轮得分之和。

请计算游戏的最大可能总得分。

输入格式

第一行两个整数 $n, m$。

接下来 $n$ 行，每行 $m$ 个非负整数，表示矩阵内容。

输出格式

一行一个整数，表示最大总得分。

样例

2 3
1 2 3
3 4 2

82

提示

对于 $60\%$ 的数据，$1 \le n, m \le 30$，答案不超过 $10^{16}$。

对于 $100\%$ 的数据，$1 \le n, m \le 80$，$0 \le a_{i,j} \le 1000$。