[SNOI2019]通信
题号：NC50788
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

n个排成一列的哨站要进行通信。第i个哨站的频段为a_i。
每个哨站i需要选择以下二者之一：
  • 直接连接到控制中心，代价为W；
  • 连接到前面的某个哨站j(j<i)，代价为。
每个哨站只能被后面的至多一个哨站连接。
请你求出最小可能的代价和。

输入描述:

第1行两个自然数n,W，分别表示哨站个数和连接到控制中心的代价；
第2行n个由空格分隔的自然数依次表示每个哨站的频段。

输出描述:

输出1行1个自然数表示答案。
示例1

输入

复制 
6 7
8 4 6 1 3 0

输出

复制 
23

说明

如果用0表示控制中心，最优方案中每个哨站向前连接的哨站依次为0,0,1,2,3,4。
示例2

输入

复制 
8 4
0 4 2 6 1 5 3 7

输出

复制 
18
示例3

输入

复制 
100 531063
868483 100818 599407 704404 691662 782990 647491 218122 906201 12145 213363 595660 501106 833711 287575 619422 507402 420930 732686 870198 446826 342144 292424 902348 925183 212446 955363 378479 596174 309751 998582 455254 992178 633810 778478 946660 884959 402342 385986 494727 398344 203903 470147 725470 227967 913015 951620 354755 197540 876065 52845 937399 823696 923941 600611 770238 296406 287789 848913 469593 641739 79570 275816 380754 95083 729424 35970 951734 833884 510971 854659 580018 428193 939020 990682 680852 886057 204917 230803 764275 803010 226704 709978 844136 709941 869203 634743 296404 480722 605047 803899 484430 637481 230117 731240 308602 309554 696800 755081 682448

输出

复制 
7292623

备注:

对于所有数据，。
对于的数据，；
对于另外的数据，；
对于另外的数据，；
对于另外的数据，；
对于另外的数据，；
对于余下的数据，无特殊限制。