問題文

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

Xは神経衰弱で遊ぶこととマラソンをすることが大好きです。ある日、Xは神経衰弱と長距離走を組み合わせた新たなゲームで遊ぶことにしました。

\(1\) 以上 \( \lfloor N/2 \rfloor \) 以下の整数がひとつ書かれているカードを大量に用意し、シャッフル後に裏向きに積んで作られた山札が \(N\) 個あります。

山札は横一列に等間隔で並んでいて、左から順に山札 \(0, 1, \cdots, N-1\) とします。

Xは山札の上を動き回り、二連続で同じ値のカードを見たらそれらのカードをペアで取り除いてスコアを獲得します。

ゲーム開始時、Xは山札 \(0\) の上にいて、初期スコアは \(0\) です。

Xは、移動可能な総距離 \(T\) を超えない範囲で以下の一連の操作を繰り返し行うことができます。

• 操作開始時にXがいる山札の番号を \(p\) とします。
• 山札 \(p\) の一番上のカードが表向きであれば、その整数を \(a_p\) とします。
（一番最初の操作時、および、後述のペアで取り除いた直後の移動時は、山札 \(p\) の一番上のカードは裏向きです。）
• 山札 \(q ( 0 \leq q \leq N-1) \) をひとつ選び、 山札 \(p\) から山札 \(q\) の上に移動します。（ \(q = p\) でもかまいません。）この時の移動距離は \(|p - q|\) です。
• 山札 \(q\) の一番上のカードを表向きにし、そのカードに書かれている整数を \(a_q\) とします。
• 表向きで存在する二枚のカードの値が等しい場合は、そのカードをペアで取り除いてカードに書かれた整数分のスコアを得ます。つまり、\(p \neq q\) かつ\( a_p = a_q \) の場合、山札 \(p, q\) の一番上からカードを1枚ずつ取り除き、スコアが \(a_p\) だけ加点されます。カードを取り除いた後のそれぞれの山札の一番上には、必ず新たなカードが裏向きで存在します。
• ペアで取り除けなかった場合、表向きで存在するカードが二枚あれば、先に表向きにしたカードが裏向きに戻ります。つまり、 \(p \neq q\)の時に、山札 \(p\) の一番上のカードが裏向きになります。

Xが得るスコアがなるべく大きくなるようにXを動かしてください。

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

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

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

各カードに書かれた整数は一様乱数にしたがって生成されます。

入出力例

4 6

0

1

2

2

1

2

1

2

2

1

0

1

-1

テスター

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

テスター