U736583 K - 御坂网络

你爱我，我爱你，御坂妹妹daisuki~~~

$n$ 个排成一列的御坂妹妹需要进行通信。第 $i$ 个御坂妹妹的频段为 $a_i$。 每个御坂妹妹 $i$ 需要选择以下两种连接方式之一： 1. 直接连接到御坂网络，代价为 $W$； 2. 连接到前面的某个御坂妹妹 $j$ $(j

第一行输入两个整数 $n$ , $W$，分别表示御坂妹妹的数量和直接连接到御坂网络的代价。 第二行输入 $n$个整数： $a_1,a_2,\dots,a_n$ 其中 $a_i$ 表示第 $i$ 个御坂妹妹的频段。

输出一行一个整数，表示最小可能的总代价。

#### **数据范围** 对于所有测试数据： $1\leq n\leq1000$ $0\leq W,a_i\leq10^9$ 此外： - 对于 $10\%$ 的数据，$n\leq10$； - 对于另外 $10\%$ 的数据，$n\leq20$； - 对于另外 $20\%$ 的数据，$n\leq50$，$W\leq5$，$a_i\leq4$； - 对于另外 $20\%$ 的数据，$n\leq100$； - 对于另外 $20\%$ 的数据，$n\leq300$； - 对于余下 $20\%$ 的数据，无特殊限制。