g6-08106. 木料切段 未做

木材厂收到一根长 $n$ 米的木料，可以切成若干段出售，每段长度都是正整数米。长度为 $i$ 米的一段能卖 $p_i$ 元；每切一刀要付 $c$ 元加工费，切成 $t$ 段就要切 $t-1$ 刀（不切就不用付）。求卖完这根木料最多能净赚多少钱。

第一行两个整数 $n$、$c$。

第二行 $n$ 个整数 $p_1,p_2,\dots ,p_n$。

一行一个整数，表示最大净收入。

输入 1

5 1
1 5 8 9 10

输出 1

12

切成 2 米和 3 米两段，卖 $5+8=13$ 元，付 1 刀加工费 1 元，净赚 12 元；整根不切只能卖 10 元。

$1\le n\le 2000$，$0\le c\le 10^4$，$0\le p_i\le 10^4$。保证答案在 64 位整数范围内。