#9311. 「USACO11DEC」Umbrellas for Cows S 提高+/省选−

今天是个雨天！

农夫约翰的 头奶牛，编号 ，并不喜欢被雨淋湿。

共有 个无顶牛棚排成一条直线，将该直线视作 轴，所有牛棚的坐标从 到 。

奶牛 位于坐标 的牛棚中。

所有奶牛都在不同的牛棚。

为了保护奶牛免受雨淋，约翰想给它们购买雨伞。

一把覆盖坐标 到 的伞的宽度为 。

宽度为 的雨伞的价格为 。

大伞不一定比小伞贵。

请帮助约翰计算，购买一套雨伞，从而保护每头奶牛都免受雨淋，所需要的最低花费。

请注意，最佳解决方案中的雨伞之间可能出现覆盖区域的重叠。

第一行包含两个整数 和 。

接下来 行，每行包含一个整数 。

接下来 行，其中第 行包含一个整数 。

输出购买雨伞所需的最低花费。

样例输入

6 12
1
2
11
8
4
12
2
3
4
4
8
9
15
16
17
18
19
19

样例输出

9

样例解释

共需要宽度为 的雨伞各一个。

牛的分布，以及雨伞的位置如下：

UUUUUUUUUU           U        UUUU
C  C     C           C        C  C
|--|--|--|--|--|--|--|--|--|--|--|
1  2  3  4  5  6  7  8  9  10 11 12

,
,
,