Problem Statement

A fairy performs by following a musical score. The score is a sequence of notes placed one at a time, and playing a certain note right after a certain note earns a fixed score. You are given the number n of notes to write in the score, the number m of kinds of notes, and a table showing how much score is added when a certain note is played right after a certain note. From these two pieces of data, find the score obtained when writing the musical score that gives the maximum score. A musical score is evaluated by the simple sum of the scores.

Input

$n$
$m$
$A_{11}$$\dots$$A_{1m}$
$\dots$
$A_{m1}$$\dots$$A_{mm}$

$1 \leq n \leq 5 \times 10^{9}$
$2 \leq m \leq 30$
$0 < A_{i,j} \leq100$
$A_{i,j}$ means that playing the note of kind j after the note of kind i earns a score of $A_{i,j}$ points.
However, since the fairy dislikes consecutive identical notes, $A_{i,i}$=0
You may assume that $A_{i,j}$ is an integer.

Output

Print a newline at the end.

Sample

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

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