该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

输入文件: play.in 输出文件: play.out
时间限制: 1 Sec 内存限制: 256 MB

题目描述

小明会按照乐谱进行演奏。

这是由音符一个接一个排列而成的乐谱，当奏出某个音之后的下一个音时，就能获得固定的分数。

乐谱中应编写的音符个数 $n$、音的种类数 $m$，以及“奏出某个音之后的下一个音时会追加多少分数”的对照表。

请根据这两组数据，求出编写乐谱时能得到最大分数的情况下，该最大分数是多少。

乐谱的评分方式为分数的简单相加。

输入格式

第一行一个整数 $n$。

第二行一个整数 $m$。

接下来 $m$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数 $A_{ij}$ 表示在第 $i$ 种音之后弹出第 $j$ 种音会追加的分数。

输出格式

一个整数，表示小明能够得到的最大分数。

样例

7
4
0 20 10 100
10 0 100 10
100 10 0 10
10 100 20 0

600

样例说明 #1

乐谱为 $1 \ 4 \ 2 \ 3 \ 1 \ 4 \ 2$，可以得到 $600$ 分。

177
10
0 1 2 9 10 10 6 7 10 5
4 0 5 3 5 1 4 4 10 4
8 7 0 8 2 5 5 2 6 6
8 7 3 0 5 1 6 5 8 2
1 6 1 7 0 9 8 5 3 5
1 2 7 4 9 0 10 5 5 9
3 3 8 6 8 8 0 9 2 10
2 5 7 7 1 9 7 0 6 10
9 1 4 4 5 7 6 4 0 3
1 4 3 8 4 9 1 1 3 0

1702

123
12
0 45 21 74 60 97 45 10 71 70 76 8
57 0 1 13 49 23 61 58 52 35 39 34
89 53 0 95 86 61 72 98 88 78 47 77
66 7 42 0 25 14 23 11 25 34 94 53
60 57 41 16 0 86 10 23 64 23 53 76
78 7 48 37 30 0 18 87 73 7 51 31
99 57 65 96 83 36 0 73 33 84 28 74
69 59 62 47 6 33 55 0 19 13 34 25
14 32 97 17 47 20 46 23 0 58 32 68
28 50 74 74 32 25 63 84 41 0 80 20
44 42 1 95 68 32 8 1 71 91 0 11
54 86 48 84 53 80 48 45 5 90 26 0

11532

数据范围

• 对于 20% 的数据，$n \leq 10$。
• 对于 55% 的数据，$n \leq 100$。
• 对于 70% 的数据，$n \leq 200$。
• 对于 85% 的数据，$n \leq 2000$。
• 对于 100% 的数据，$1 \leq n \leq 5 \times 10^9$，$2 \leq m \leq 30$，$\forall i \neq j, 0 < A_{ij} \leq 100$，保证 $A_{ii} = 0$。