题目描述

今天是一个雨天！农夫约翰有 $N (1 \le N \le 5,000)$ 头奶牛，编号为 $1,2,\cdots ,N$，它们并不特别喜欢淋湿。奶牛们站在一排没有屋顶的牛棚里，这些牛棚沿着一条数轴排列。牛棚的 $X$ 坐标从 $1$ 到 $M (1 \le M \le 10^5)$。牛 $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 <= C_W <= 10^6)$ 元。大雨伞并不一定比小雨伞贵。

请你帮农夫约翰找到购买一组雨伞以保护每头奶牛免受雨淋的最低成本。注意，最优方案中的雨伞集合可能会有一定程度的重叠。

输入格式

第 $1$ 行，是两个用空间分隔的整数：$N$ 和 $M$。

接下来 $N$ 行，每行包含一个整数，第 $i+1$ 行的数表示 $X_i$，为第 $i$ 头奶牛所在的点的坐标值。

接下来 $M$ 行，第 $N+j+1$ 行包含一个整数：$C_j$。

输出格式

仅一行，一个整数，表示最低的成本。

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

9 

提示

样例解释：

共有 $12$ 个牛棚，其中第 $1,2,4,8,11$ 和 $12$ 号牛棚有牛。覆盖一个摊位的伞要花费 $2$，覆盖两个摊位的伞要花费 $3$，以此类推。通过购买一个宽度 $4$ 的伞、一个宽度为 $1$ 的伞和一个宽度为 $2$ 的伞，可以以 $4 + 2 + 3 = 9$ 的成本覆盖所有牛：

其中 $C$ 代表一头牛，$U$ 代表伞。