J19 习题-4 Null老师度假

题目描述

忙碌了一个学期的 Null 老师 决定奖励自己 $N$ 天假期。假期中不同的穿衣方式会有不同的快乐值。 已知 Null 老师 一共有 $M$ 件衬衫，且如果昨天穿的是衬衫 $A$，今天穿的是衬衫 $B$，则 Null 老师 今天可以获得 $f[A][B]$ 快乐值。 在 $N$ 天假期结束后， Null 老师 最多可以获得多少快乐值？

输入格式

包含多组测试样例，每组测试样例格式描述如下： 第一行给出两个整数 $N$,$M$，分别代表假期长度与 $Null$ 老师 的衬衫总数。 接下来 $M$ 行，每行给出 $M$ 个整数，其中第 $i$ 行的第 $j$ 个整数，表示 $f[i][j]$。 测试样例组数不会超过 $10$。

输出格式

每组测试样例输出一行，表示 Null 老师 可以获得的最大快乐值。

样例输入

3 2
0 1
1 0
4 3
1 2 3
1 2 3
1 2 3

样例输出

2
9

数据范围

$100\%$ 的数据：$2 \le N \le 100000$, $1 \le M \le 100$，$1 \le f[i][j] \le 1000000$。