問題文

この問題はインタラクティブ形式です。

Xはすごろく遊びが大好きで、毎日ひとりですごろく遊びをしています。
ある日、Xは普通のすごろくはマスの内容があらかじめわかっているのがつまらないと感じ、新たなすごろくゲームで遊ぶことにしました。

• このすごろくは1列に並んだ \(N + 1\) マスからなっています。
• マスには順に \(0, 1, ..., N\) と番号が振られています。\(0\) 番目のマスがスタートで、\(N\) 番目のマスがゴールです。
• サイコロを振ってその出目の値だけゴールに向かって進みます。
  ゴールを通り過ぎる場合は、通り過ぎたぶんスタート方向へ折り返します。（具体的には入出力例をご覧ください）
• ゴールにぴったり到達したら、またスタートからゴールを目指すのを繰り返します。
• \(i\) 番目のマスには整数 \(V_i\) が書かれていて、マスに止まるとそこに書かれている整数がスコアとして加算されます。
• 一度ゴールに到達して再スタートしたあとも \(V_i\) の値は変わりませんが、\(i\) 番目のマスにはじめて止まるまでは \(V_i\) の値はわかりません。
• ゲーム開始時、Xはスタートにいて、初期スコアは \(0\) です。

Xはサイコロを \(M\) 回振って遊ぶことにしましたが、ゲームをより面白くするためにサイコロにも一工夫を加えることにしました。

• Xが使うサイコロは、偏りのない6面サイコロで、各面の値は\(1, 2, 3, 4, 5, 6\)となっています。
• Xは毎回サイコロを振る前に、サイコロのどれかひとつの面を \(1 \sim 6\) の好きな整数に変えることができます。サイコロの目の変化はそれ以降も継続します。

どうサイコロの目を設定したらよいかわからないXのかわりに、
Xが得るスコアがなるべく大きくなるように、サイコロの目を設定しながらすごろく遊びをしてください。

各テストケースの得点およびこの問題の得点は、次のように計算されます。

• 1つのテストケースでは、Xが得たスコアがそのまま得点になります。
• テストケースは全部で 50 個あります。各テストケースの得点の合計が、この問題の得点になります。

テストケースの生成について

V_N = 5000 です。
そのほかの V_i については、値が大きい領域と値が小さい領域ができるよう、初期値を\(0\)とし、次の処理を\(100\)回行って設定しています。

1. \([1, 10]\) の整数を一様分布から選び、 \(l\) とする
2. \([1, N-5-l]\) の整数を一様分布から選び、 \(p\) とする
3. \([1, 200]\) の整数を一様分布から選び、 \(v\) とする
4. \(V_p ... V_{p+l-1}\) に対して \(v\) を加える

とくに、 \(V_{0} = V_{N-5} = V_{N-4} = V_{N-3} = V_{N-2} = V_{N-1} = 0\) です。

入出力例

20 6

1 2 3 4 6 6

6 263 6

1 2 3 4 6 6

3 132 9

1 2 3 6 6 6

6 0 15

1 2 6 6 6 6

6 0 19

1 2 6 6 6 3

1 5000 20

1 2 6 3 6 3

6 263 6

テスター

次のリンクから提供しています。

テスター