思路：状态压缩动态规划

大家需要先学习掌握二进制集合操作

dp[i][j]代表第i天选了状态为j的地方采蘑菇能得到的最大值，然后二重循环枚举当天的状态和上一天的状态，检查合法的取max转移

具体的，如果k的第i位为1，那么j的第i-1位和第i+1位不能为1

题目内容

小红每天都会去$n$个地方采蘑菇，这些地点连成一条直线编号为$1$~$n$

如果小红今天在$i$地采了蘑菇，那么他第二天将不能在$i-1$,$i$,$i+1$这三地采蘑菇。

现在给你$m$天每天每个地点产生的蘑菇数量，小红每天可以选择多个地方采蘑菇。你能求出小红最多能采多少蘑菇吗？

输入描述

第一行输入两个整数 $n$，$m$（$1≤n≤7$;$1≤m≤100$）表示地点数、天数。

此后$m$行，第$i$行输入$n$个整数$a_1,a_2,...,a_i,...a_n$($1≤a_i≤10^3$)表示第$i$天$j$地点的蘑菇数量。

输出描述

在一行上输出一个整数，代表小红最多能采的蘑菇数量。

样例1

输入

3 3
1 2 3
4 5 6
7 8 9

输出

30

说明

第一天采位置$1，2，3$，第二天不采，第三天采位置$1，2，3$

样例2

输入

3 3
10 1 1
3 6 10
1 1 1

输出

21

说明

第一天采位置$1$，第二天采$3$，第三天采$1$