No.572 妖精の演奏

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : horiesinitihoriesiniti / テスター : はむこはむこ
7 ProblemId : 1216 / 出題時の順位表

問題文

妖精が譜面に従って演奏をします。 音符が一個ずつならんだ譜面で、ある音の次にある音をならすと一定のスコアが手に入ります。 譜面に書くべき音符の数n個と音の種類数m、ある音の次にある音を鳴らすといくらのスコアが加算されるかの表が与えられます。 この二つのデータから最大スコアとなる譜面を書いたときのスコアを求めて下さい。 譜面の評価はスコアの単純合計です。

入力

$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}$はi種類目の音の後にj種類目の音を鳴らすと$A_{i,j}$点のスコアが入るという意味である。
ただし妖精は同じ音の連続を嫌うので$A_{i,i}$=0
$A_{i,j}$は整数と仮定してよい。

出力

最後に改行してください。

サンプル

サンプル1
入力
7
4
0 20 10 100
10 0 100 10
100 10 0 10
10 100 20 0
出力
600

1 4 2 3の音の繰り返しである。

サンプル2
入力
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

サンプル3
入力
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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。