题目内容

在一个线性排列的实验站中，有 $n$ 个数据采集装置，按顺序编号为 $1$ 到 $n$。研究员计划进行 $m$ 天的数据收集工作。每一天，研究员可以任意选择一些装置进行激活并收集数据，每个装置在当天会产生一定数量的数据。

由于装置之间存在电磁干扰，存在如下约束：若某一天激活了编号为 $i$ 的装置，则第二天不能激活装置 $i-1$、$i$ 以及 $i+1$（若这些编号存在）。也就是说，相邻两天中，不允许存在位置相邻或有重叠的激活装置。

给定未来 $m$ 天中，每天每个装置将会产生的数据量，请你计算研究员在这 $m$ 天内最多能收集到的总数据量。

约束条件：装置数量 $n$ 满足 $1 \le n \le 7$，天数 $m$ 满足 $1 \le m \le 100$，每天每个装置的数据量均为正整数且不超过 $10^3$。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示装置数量和天数。 接下来 $m$ 行，每行包含 $n$ 个整数，依次表示当天装置 $1$ 到装置 $n$ 产生的数据量。

输出描述

输出一个整数，表示研究员在 $m$ 天内能够收集的最大总数据量。

样例1

输入

1 1
5

输出

5

说明

只有 1 天，且只有一个装置。没有相邻天的约束，研究员可以直接激活装置 $1$，获得数据量 $5$，这也是该天的最大数据量。因此最大总数据量为 $5$。

样例2

输入

2 2
1 2
3 4

输出

7

说明

第 1 天装置数据量为 $[1, 2]$，第 2 天为 $[3, 4]$。由于相邻两天不能有位置相邻或重叠的激活装置，如果第 1 天激活了装置 $1$ 或 $2$，第 2 天将无法激活任何装置（装置 $1$ 禁止 $1$ 和 $2$，装置 $2$ 禁止 $1$ 和 $2$）。 最优策略是第 1 天不激活任何装置，这样第 2 天可以同时激活装置 $1$ 和 $2$，获得 $3 + 4 = 7$ 的数据量，总数据量达到 $0 + 7 = 7$，这是可能的最大值。

样例3

输入

3 3
1 2 1
1 10 1
1 1 1

输出

10

说明

三天数据量分别为 $[1, 2, 1]$，$[1, 10, 1]$，$[1, 1, 1]$。第 2 天的装置 $2$ 数据量 10 非常突出，但受前后相邻天约束限制。 若第 1 天不激活任何装置，第 2 天可以单独激活装置 $2$，获得 $10$；此时第 2 天的激活会禁止第 3 天激活装置 $1$、$2$ 和 $3$（因装置 $2$ 在相邻天会限制自身及相邻位置），故第 3 天数据量为 $0$，总数据量为 $10$。 若第 1 天激活装置 $2$，则第 2 天完全不能激活，总数据量仅为 $2$ 左右；其他任何选择均无法超过 $10$。因此最大总数据量为 $10$。

样例4

输入

7 1
1 2 3 4 5 6 7

输出

28

说明

这里只有 1 天，且 7 个装置都可以独立工作，没有相邻天的限制。研究员可以将全部装置激活，收集所有数据，总数据量为 $1+2+3+4+5+6+7=28$。