P3035 [USACO11DEC] Umbrellas for Cows S

今天是一个雨天！农夫约翰有 $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

第 $1$ 行，是两个用空间分隔的整数：$N$ 和 $M$。 接下来 $N$ 行，每行包含一个整数，第 $i+1$ 行的数表示 $X_i$，为第 $i$ 头奶牛所在的点的坐标值。 接下来 $M$ 行，第 $N+j+1$ 行包含一个整数：$C_j$。

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

样例解释： 共有 $12$ 个牛棚，其中第 $1,2,4,8,11$ 和 $12$ 号牛棚有牛。覆盖一个摊位的伞要花费 $2$，覆盖两个摊位的伞要花费 $3$，以此类推。通过购买一个宽度 $4$ 的伞、一个宽度为 $1$ 的伞和一个宽度为 $2$ 的伞，可以以 $4 + 2 + 3 = 9$ 的成本覆盖所有牛： | 牛棚 |< |< |< |< |< |< |< |< |< |< |< | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| |U |< |< |< | | | |U | | |U |< | |C |C | |C | | | |C | | |C |C | |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12| 其中 $C$ 代表一头牛，$U$ 代表伞。