B - 縞模様 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

小学生の高橋君は、縞模様が大好きです。今、高橋君は、左から右に一直線上に並んだ n 枚の色画用紙を眺めています。高橋君は縞模様がとても好きなので、いくつかの画用紙を絵の具で新しい色に塗り替えることで、全体に見て縞模様になっているようにしたいと思っています。

全体的に見て縞模様であるとは、全体で使用される色がちょうど 2 つであって、全ての画用紙についてそれと隣り合う画用紙との色が異なっている状態のことを指します。

あなたの仕事は、既に配置されている画用紙の枚数 n と、1 枚の画用紙を別の色に塗り替えるためにかかる絵の具の費用 c が与えられるので、縞模様の達成に必要な合計費用の最小値を出力するプログラムを作ってあげることです。 この問題では便宜上、それぞれの色が 1 ～ 10 の 10 種類の数として与えられます。塗り替えるために使える絵の具の色もこの 10 種類のみです。

入力

入力は以下の形式で標準入力から与えられる。 

n　c
a_1
a_2
:
a_n
  • 1 行目には、画用紙の枚数を表す整数 n (2 ≦ n ≦ 100) と、画用紙を 1 枚塗り替えるために必要な絵の具の費用 c (1 ≦ c ≦ 1000) が与えられる。
  • 2 行目から n 行では、既に配置された画用紙の色がそれぞれ与えられる。このうち i 行目では一直線上に並んだ画用紙のうち左から i 番目の色をそれぞれ表す整数 a_i (1 ≦ a_i ≦ 10) が与えられる。

出力

縞模様を達成するのに必要な合計費用の最小値を 1 行に出力せよ。出力の末尾にも改行をいれること。

入力例1 

3 10
3
2
1

出力例1 

10

塗られている色は、左から順番に 3,2,1 である。1 番目の「3」を「1」に塗り替えれば 1,2,1　となる。また、3 番目の「1」を「3」に塗り替えれば 3,2,3 となる。

これらはどちらも縞模様を達成していて、かつどちらの場合も 1 枚の画用紙を塗り替える必要があり、合計費用は 10 である。従って 10 を出力すればよい。

入力例2 

4 100
1
1
1
1

出力例2 

200

入力例3 

10 1000
1
2
3
4
5
6
7
8
9
10

出力例3 

8000