Umbrellas for Cows

It is a rainy day. Farmer John's $N$ ($1 \le N \le 5{,}000$) cows, numbered $1 \ldots N$, do not like getting wet. The cows stand in roofless stalls arranged along a number line. The stalls occupy the integer coordinates from $1$ to $M$ ($1 \le M \le 100{,}000$). Cow $i$ stands at coordinate $X_i$ ($1 \le X_i \le M$), and no two cows share a stall.

To keep the cows dry, Farmer John wants to buy umbrellas. An umbrella that spans coordinates $X_i$ to $X_j$ (with $X_i \le X_j$) has width $X_j - X_i + 1$. An umbrella of width $W$ costs $C_W$ ($1 \le C_W \le 1{,}000{,}000$). A wider umbrella is not necessarily more expensive than a narrower one.

Find the minimum total cost of a set of umbrellas that keeps every cow dry. In an optimal solution the umbrellas may overlap.

• The first line contains two space-separated integers $N$ and $M$.
• Each of the next $N$ lines contains one integer $X_i$.
• Each of the following $M$ lines contains one integer; the $j$-th of these lines is $C_j$, the cost of an umbrella of width $j$.

• Print a single integer: the minimum cost required to buy umbrellas that keep all cows dry.

There are $12$ stalls, and cows occupy stalls $1$, $2$, $4$, $8$, $11$, and $12$. An umbrella covering one stall costs $2$, one covering two stalls costs $3$, and so on.

By buying a width-$4$ umbrella, a width-$1$ umbrella, and a width-$2$ umbrella, all cows can be covered for a total cost of $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

Here C marks a cow and U marks part of an umbrella.