Pada! $N$ krów Farmer John ($1 \le N \le 5,000$), numery $1..N$, nie lubi moknąć. Boksy bez dachów stoją na osi o współrzędnych $X$ od 1 do $M$ ($1 \le M \le 100,000$). Krowa $i$ stoi w $X_{i}$ ($1 \le X_{i} \le M$), nie dzielą boksów.

Chce parasole. Od $X_{i}$ do $X_{j}$ ($X_{i} \le X_{j}$) szerokość to $X_{j} - X_{i} + 1$. Szerokość $W$ kosztuje $C_W$ ($1 \le C_{W} \le 1,000,000$). Większe niekoniecznie droższe.

Znajdź minimalny koszt zestawu chroniącego wszystkie. Optymalne parasole mogą się nakładać.

Wejście

• Wiersz 1: całkowite $N$, $M$ ze spacją.
• Wiersze $2..N+1$: wiersz $i+1$ zawiera całkowite $X_{i}$.
• Wiersze $N+2..N+M+1$: wiersz $N+j+1$ zawiera całkowite $C_{j}$.

Wyjście

• Wiersz 1: całkowity minimalny koszt dla wszystkich krów.

Przykład

Wejście 1

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

Wyjście 1

9

Uwagi

Jest 12 boksów, zajęte w 1, 2, 4, 8, 11, 12. Osłona jednego kosztuje 2, dwóch 3 i tak dalej.

Po jednym szerokości 4, 1, 2 osłonią wszystkie za $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

$C$ oznacza krowę, $U$ część parasola.

Autor zadania: Alex Chen, 2011