今日は雨です！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