题目描述

今天是个下雨天！$\red{Farmer John }$的 $\red{N (1 <= N <= 5,000) }$头奶牛，编号为 $\red{1..N，}$并不特别喜欢弄湿。奶牛站在数轴上排列的无顶棚中。这些摊位的 $\red{X }$坐标从 $\red{1 }$到 $\red{M (1 <= M <= 100,000)}$。奶牛 $\red{i }$站在坐标 $\red{X_i (1 <= X_i <= M) }$上的摊位上。没有两头奶牛共用摊位。

为了保护奶牛免受雨淋，农夫约翰想给它们买雨伞。跨坐标 $\red{X_i }$到 $\red{X_j (X_i <= X_j) }$的伞的宽度为 $\red{X_j - X_i + 1}$。购买宽度为 $\red{W }$的伞需要花费 $\red{C_W (1 <= C_W <= 1,000,000)}$。更大的雨伞不一定要花费比小雨伞还多。

帮助农夫约翰找出购买一套可以保护每头牛免受雨淋的雨伞的最低成本。请注意，最佳解决方案中的伞集可能会在某种程度上重叠。

在 $\red{X }$数轴上有 $\red{M }$个整数点，点的坐标分别是 $\red{1 }$至 $\red{M}$。有 $\red{N（}$$\red{1<= N<= 5000）}$只奶牛，编号为 $\red{1.. N，}$第 $\red{i }$只奶牛所在的整数点坐标是 $\red{Xi（}$$\red{1<= Xi <= M <= 100,000）}$, 没有两头奶牛在相同的点上。现在正在下雨，为了保护奶牛，$\red{FJ }$需要购买很多把雨伞，把所有的奶牛都遮住。如果一把雨伞能遮住坐标是 $\red{a }$到坐标 是 $\red{b }$的这一段（$\red{a<=b）}$，那么这把雨伞的宽度就是 $\red{b-a+1}$。现在我们给出购买宽度是 $\red{1 }$的雨伞的价格，购买宽度是 $\red{2 }$的雨伞的价格，…购买宽度是 $\red{M }$的雨伞 的价格。

这里特别需要注意：宽度更大的雨伞的价格不一定超过宽度较小的雨伞，这完全取决于读入数据。你的任务是帮助 $\red{FJ }$找到购买雨伞最低的成本，使得这些雨伞能把所有的奶牛遮住，从而不淋雨。需要注意 的是最佳的解决方案雨缮能会重叠。

输入格式

第 $\red{1 }$行：两个空格分隔的整数：$\red{N }$和 $\red{M}$。

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行包含一个整数：$\red{X_i}$。

第 $\red{N+2..N+M+1 }$行：第 $\red{N+j+1 }$行包含一个整数：$\red{C_j}$。

第 $\red{1 }$行：两个空间分隔的整数：$\red{N }$和 $\red{M}$。

下来有 $\red{N }$行，包含一个整数：$\red{Xi，}$表示第 $\red{i }$头奶牛所在的点的坐标值。

接下来有 $\red{M }$行：每行包含一个整数 $\red{Ci，}$表示购买宽度是 $\red{i }$的雨伞的价格是 $\red{Ci }$元。

输出格式

第 $\red{1 }$行：一个整数，是为所有奶牛购买雨伞所需的最低成本。

一个整数，是最低的成本。

样例

输入样例

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

输出样例

9

提示

有 $\red{12 }$个摊位，第 $\red{1}$、$\red{2}$、$\red{4}$、$\red{8}$、$\red{11 }$和 $\red{12 }$个摊位有奶牛。一把伞覆盖一个摊位的费用为 $\red{2，}$一把伞覆盖两个摊位的费用为 $\red{3，}$以此 类推。

通过购买 $\red{4 }$号雨伞、$\red{1 }$号雨伞和 $\red{2 }$号雨伞，可以以 $\red{4+2+3=9 }$的成本覆盖所有奶牛：

$\red{UUUUUUUUU UUUUU}$

中国交建

$\red{|--|--|--|--|--|--|--|--|--|--|--| 1 2 3 4 5 6 7 8 9 10 11 12}$

$\red{C}$代表牛，$\red{U}$代表伞的一部分。

$\red{1}$、 买一把长度是 $\red{4 }$的雨伞去遮住坐标在 $\red{1}$、$\red{2}$、$\red{4 }$的三头奶牛，费用是 $\red{4}$；

$\red{2}$、 买一把长度是 $\red{1 }$的雨伞遮住坐标在 $\red{8 }$的奶牛，费用是 $\red{2}$；

$\red{3}$、 买一把长度是 $\red{2 }$的雨伞遮住坐标在 $\red{11}$、$\red{12 }$的两头奶牛，费用是 $\red{3}$。

总费用是 $\red{4 +2+ 3 = 9}$