今天下雨！Farmer John 的 $N$ 头奶牛（$1 \le N \le 5,000$），编号 $1..N$，不喜欢淋湿。她们站在数轴上无顶的牛栏中，牛栏的 $X$ 坐标从 1 到 $M$（$1 \le M \le 100,000$）。奶牛 $i$ 在 $X_{i}$（$1 \le X_{i} \le M$），每栏最多一头。

他想买伞遮雨。覆盖 $X_{i}$ 到 $X_{j}$（$X_{i} \le X_{j}$）的伞宽为 $X_{j} - X_{i} + 1$。宽 $W$ 的价格为 $C_W$（$1 \le C_{W} \le 1,000,000$）。大伞未必比小伞贵。

求买一组伞保护所有奶牛的最小费用。最优方案中伞可能有些重叠。

输入格式

• 第 1 行：空格分隔的整数 $N$、$M$。
• 第 $2..N+1$ 行：第 $i+1$ 行含一个整数 $X_{i}$。
• 第 $N+2..N+M+1$ 行：第 $N+j+1$ 行含一个整数 $C_{j}$。

输出格式

• 第 1 行：一个整数，为所有奶牛买伞的最小费用。

样例

输入格式 1

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

输出格式 1

9

说明

有 12 栏，1、2、4、8、11、12 栏有奶牛。覆盖一栏的伞价 2、两栏价 3，依此类推。

买宽 4、1、2 的伞各一把，可覆盖全部奶牛，费用 $4+2+3=9$：

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

$C$ 表示奶牛，$U$ 表示伞的一部分。

题目作者：Alex Chen，2011