题目描述

Today is a rainy day! Farmer John's N (1 <= N <= 5,000) cows, numbered 1..N, are not particularly fond of getting wet. The cows are standing in roofless stalls arranged on a number line. The stalls span X-coordinates from 1 to M (1 <= M <= 100,000). Cow i stands at a stall on coordinate X_i (1 <= X_i <= M). No two cows share stalls.
In order to protect the cows from the rain, Farmer John wants to buy them umbrellas. An umbrella that spans coordinates X_i to X_j (X_i <= X_j) has a width of X_j - X_i + 1. It costs C_W (1 <= C_W <= 1,000,000) to buy an umbrella of width W. Larger umbrellas do not necessarily cost more than smaller umbrellas.
Help Farmer John find the minimum cost it takes to purchase a set of umbrellas that will protect every cow from the rain. Note that the set of umbrellas in an optimal solution might overlap to some extent.
在 X 数轴上有 M 个整数点，点的坐标分别是 1 至 M。有 N（1<= N<= 5000）只奶牛，编号为 1.. N，第 i 只奶牛所在的整数点坐标是 Xi（1<= Xi <= M <= 100,000）, 没有两头奶牛在相同的点上。现在正在下雨，为了保护奶牛，FJ 需要购买很多把雨伞，把所有的奶牛都遮住。如果一把雨伞能遮住坐标是 a 到坐标是 b 的这一段（a<=b），那么这把雨伞的宽度就是 b-a+1。现在我们给出购买宽度是 1 的雨伞的价格，购买宽度是 2 的雨伞的价格，…购买宽度是 M 的雨伞的价格。
这里特别需要注意：宽度更大的雨伞的价格不一定超过宽度较小的雨伞，这完全取决于读入数据。你的任务是帮助 FJ 找到购买雨伞最低的成本，使得这些雨伞能把所有的奶牛遮住，从而不淋雨。需要注意的是最佳的解决方案雨伞可能会重叠。

输入格式：

Line 1: Two space-separated integers: N and M.
Lines 2..N+1: Line i+1 contains a single integer: X_i.
Lines N+2..N+M+1: Line N+j+1 contains a single integer: C_j.
第 1 行：两个空间分隔的整数：N 和 M。
下来有 N 行，包含一个整数：Xi，表示第 i 头奶牛所在的点的坐标值。
接下来有 M 行：每行包含一个整数 Ci，表示购买宽度是 i 的雨伞的价格是 Ci 元。

输出格式：

Line 1: A single integer that is the minimum cost needed to purchase umbrellas for all the cows.
一个整数，是最低的成本。

输入样例#1：

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

输出样例#1：

9