Il pleut ! Les $N$ vaches de Farmer John ($1 \le N \le 5,000$), numérotées $1..N$, n'aiment pas être mouillées. Les stalles sans toit sont sur une droite aux coordonnées $X$ de 1 à $M$ ($1 \le M \le 100,000$). La vache $i$ est en $X_{i}$ ($1 \le X_{i} \le M$), sans stalle partagée.

Il veut des parapluies. De $X_{i}$ à $X_{j}$ ($X_{i} \le X_{j}$), la largeur est $X_{j} - X_{i} + 1$. Une largeur $W$ coûte $C_W$ ($1 \le C_{W} \le 1,000,000$). Les grands ne sont pas forcément plus chers.

Trouvez le coût minimal d'un ensemble protégeant toutes les vaches. Les parapluies optimaux peuvent se chevaucher.

Entrée

• Ligne 1 : entiers $N$, $M$ séparés par un espace.
• Lignes $2..N+1$ : ligne $i+1$, un entier $X_{i}$.
• Lignes $N+2..N+M+1$ : ligne $N+j+1$, un entier $C_{j}$.

Sortie

• Ligne 1 : entier du coût minimal pour toutes les vaches.

Exemples

Entrée 1

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

Sortie 1

9

Remarque

Il y a 12 stalles, occupées en 1, 2, 4, 8, 11, 12. Couvrir une stalle coûte 2, deux 3, et ainsi de suite.

Un parapluie de chaque largeur 4, 1, 2 couvre toutes les vaches pour $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$ représente une vache, $U$ une partie de parapluie.

Auteur du problème : Alex Chen, 2011