期末考试 (test)

【题目描述】

考试季开始了，小明一共需要复习 $m$ 门学科。

小明的期末季有 $n$ 天，每天他需要复习 $m$ 门学科中的一门。

小明比较喜欢学习，如果第 $i$ 天他复习了第 $j$ 门学科，他可以获得 $a_{i,j}$ 点幸福值。

但是，为了效率，小明希望相邻两天不要学习两门相同的学科。

现在小明想知道他至多能获得多少幸福值。

【输入格式】

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

接下来$n$行，每一行$m$个整数，表示数组$a_{i,j}$

【输出格式】

一个整数，表示答案

【样例 $1$ 输入】

3 3
10 40 70
20 50 80
30 60 90

【样例 $1$ 输出】

210

【样例 $2$ 输入】

7 3
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1

【样例 $2$ 输出】

46

【数据范围】

对于$20\%$的数据，$1\le n,m\le 8$.

对于$40\%$的数据，$1\le m\le 100$.

对于$100\%$的数据，$1\le n\le 100,1\le m\le 10^4,1\le a_{i,j}\le 10^5$.