問題
カードの山札が$\ N\ $個円状に置かれており、時計回りに$\ i\ $番目に置かれている山札を山札$\ i(1 \leqq i \leqq N)\ $とする。
山札$\ i\ $には$\ M\ $枚のカードがあり、山札$\ i\ $の$\ j(1 \leqq j \leqq M)\ $枚目のカードには整数$\ C_{i, j}$が書かれている。
あなたは以下の条件を満たすように山札$\ i\ $からカードを1枚ずつ選んで山札の上に置く。山札$\ i \ $から選んだカードに書かれた整数を$\ d_{i}\ $としたとき、$\displaystyle \sum_{i=1}^N d_i$の最大値はいくつになるか。
- $ \begin{eqnarray} l = \begin{cases} N & ( i = 1 ) \\ i-1 & ( i > 1 ) \end{cases} \end{eqnarray}$ としたとき、$\ d_{i}\ $と$\ d_{l}\ $は互いに素である。
- $ \begin{eqnarray} r = \begin{cases} 1 & ( i = N ) \\ i+1 & ( i < N ) \end{cases} \end{eqnarray}$ としたとき、$\ d_{i}\ $と$\ d_{r}\ $は互いに素である。
入力
入力は以下の形式で標準入力から与えられる。
$N\ M$
$C_{1, 1}\ C_{1, 2}\ \cdots\ C_{1, M}$
$C_{2, 1}\ C_{2, 2}\ \cdots\ C_{2, M}$
$\vdots$
$C_{N, 1},\ C_{N, 2},\ \cdots\ C_{N, M}$
出力
条件を満たしたときの$\displaystyle \sum_{i=1}^N d_i$の最大値を出力せよ。条件を満たすような$d_{i}$が存在しない場合は$-1$を出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leqq N \leqq 100$
- $1 \leqq M \leqq 50$
- $1 \leqq C_{i, j} \leqq 10^{9} (1 \leqq i \leqq N, 1 \leqq \ j \leqq M)$
- 入力は全て整数である
入出力例
入力例1
4 3 3 5 12 7 10 9 5 8 2 4 1 5
出力例1
32
$d_{1} = 12,\ d_{2} = 7,\ d_{3} = 8,\ d_{4} = 5$は条件を満たす。
- $\ d_{1}\ $は$\ d_{2}\ $と$\ d_{4}\ $と互いに素でなければならない。$12$と$7$, $12$と$5$の最大公約数は$1$である。
- $\ d_{2}\ $は$\ d_{3}\ $と$\ d_{1}\ $と互いに素でなければならない。$7$と$8$, $7$と$12$の最大公約数は$1$である。
- $\ d_{3}\ $は$\ d_{4}\ $と$\ d_{2}\ $と互いに素でなければならない。$8$と$5$, $8$と$7$の最大公約数は$1$である。
- $\ d_{4}\ $は$\ d_{1}\ $と$\ d_{3}\ $と互いに素でなければならない。$5$と$12$, $5$と$8$の最大公約数は$1$である。
入力例2
3 4 8 5 1 2 10 6 4 7 10 9 8 4
出力例2
24
入力例3
15 10 87 1 66 29 33 19 63 46 11 9 53 83 50 99 81 56 14 55 46 79 54 58 43 69 42 33 63 52 50 80 4 26 39 75 94 67 93 18 7 24 31 44 16 62 91 36 37 54 11 80 66 58 94 89 20 91 90 32 96 3 18 48 41 98 1 73 35 93 4 30 2 66 77 73 23 88 36 14 48 13 74 83 79 57 99 34 31 35 15 37 21 32 95 87 46 86 50 41 85 23 74 19 72 6 86 48 62 32 21 10 87 44 24 38 34 1 30 19 89 58 29 81 76 80 35 99 87 27 32 72 35 92 25 96 64 33 8 52 80 85 41 52 6 20 66 40 95 62 64 9
出力例3
1349
入力例4
4 4 2047 713 69 529 851 2231 391 46 1817 299 437 299 69 161 1909 391
出力例4
-1
入力例5
1 5 29 1 63 85 61
出力例5
1
$N = 1,\ i = 1$のときは$l = r = 1$であることに注意すること。