[ARC020B] 縞模様

题意翻译

### 题目描述 小学生的高桥喜欢条纹图案。现在,Takahashi正在寻找从左到右直线排列的n*n的彩色绘图纸。由于Takahashi非常喜欢条纹图案,所以我想通过用一种带涂料的新颜色重新绘制一些绘图纸来使它看起来像条纹一样。 作为条纹的整体观察意味着整体中使用的颜色仅为2 2并且其旁边的绘图纸的颜色与其旁边的绘图纸的颜色不同。 你的工作是给已经放置的建筑纸的数量nn和油漆的成本cc用另一种颜色替换一张绘图纸所以实现条纹的最低成本它是创建一个输出值的程序。就此而言,为方便起见,每种颜色为1~10这10个数字。可用于重新涂漆的涂料颜色也只有1~10这10种。 ### 输入输出格式 **输入格式:** 以下为标准输入格式。 ```cpp $ n c $ a1 a_1 a1​ a2 a_2 a2​ : an a_n an​ ``` - 在第一行,数字n(2≤ n ≤ 100)n(2≤n≤100)表示绘图纸的数量和重绘一张建筑纸所需的油漆成本c (1 ≤ c ≤ 1000)给出c(1≤c≤1000)。 - 在第2行到第nn行中,分别给出了已经排列的绘图纸的颜色。 在这些i i行中,整数a_i (1 ≤ a _ i ≤ 10)表示在直线a上对齐的绘图纸左边的第i种颜色 **输出格式:** 输出在第1行中实现条纹图案所需的总成本的最小值,并 在结尾输出一个回车。

题目描述

[problemUrl]: https://atcoder.jp/contests/arc020/tasks/arc020_2 小学生の高橋君は、縞模様が大好きです。今、高橋君は、左から右に一直線上に並んだ $ 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

输入样例 #2

4 100
1
1
1
1

输出样例 #2

200

输入样例 #3

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

输出样例 #3

8000

说明

### Sample Explanation 1 塗られている色は、左から順番に $ 3,2,1 $ である。$ 1 $ 番目の「3」を「1」に塗り替えれば $ 1,2,1 $ となる。また、$ 3 $ 番目の「1」を「3」に塗り替えれば $ 3,2,3 $ となる。 これらはどちらも縞模様を達成していて、かつどちらの場合も $ 1 $ 枚の画用紙を塗り替える必要があり、合計費用は $ 10 $ である。従って $ 10 $ を出力すればよい。