#PQJ61x356. QOJ 61_356
QOJ 61_356
个排成一列的哨站要进行通信。第 个哨站的频段为 。
每个哨站 需要选择以下二者之一:
直接连接到控制中心,代价为 ;
连接到前面的某个哨站 (),代价为 。
每个哨站只能被后面的至多一个哨站连接。
请你求出最小可能的代价和。
输入格式
第 行两个自然数 ,分别表示哨站个数和连接到控制中心的代价;
第 行 个由空格分隔的自然数 依次表示每个哨站的频段。
输出格式
输出 行 个自然数表示答案。
样例数据
样例 1 输入
6 7 8 4 6 1 3 0
样例 1 输出
23
样例 1 解释
如果用 表示控制中心,最优方案中每个哨站向前连接的哨站依次为 。
样例 2 输入
8 4 0 4 2 6 1 5 3 7
样例 2 输出
18
子任务
对于所有数据,。
对于 的数据,;
对于另外 的数据,;
对于另外 的数据,;
对于另外 的数据,;
对于另外 的数据,;
对于余下 的数据,无特殊限制。