题目内容

小塔每天都会去$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$