今天下雨！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