题目描述

ak机每天都会去$n$个地方采蘑菇，这些地点连成一条直线编号为$1\sim n$,如果ak机今天在$i$地采了蘑菇，那么他第二天将不能在$i-1,i,i+1$这三地采蘑菇。

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

输入描述

第一行输入两个整数 $n,m(1\le n\le 7,1\le m\le 100)$表示地点数、天数。

此后$m$行，第$i$行输入$n$个整数$a_1,a_2,...a_n(1\le a_i\le 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$