¡Llueve! Las $N$ vacas de Farmer John ($1 \le N \le 5,000$), numeradas $1..N$, no quieren mojarse. Los establos sin techo están en una recta con coordenadas $X$ de 1 a $M$ ($1 \le M \le 100,000$). Vaca $i$ está en $X_{i}$ ($1 \le X_{i} \le M$), sin compartir establos.

Quiere paraguas. De $X_{i}$ a $X_{j}$ ($X_{i} \le X_{j}$) el ancho es $X_{j} - X_{i} + 1$. Ancho $W$ cuesta $C_W$ ($1 \le C_{W} \le 1,000,000$). Los grandes no necesariamente cuestan más.

Encuentra el coste mínimo de un conjunto que proteja a todas. Los paraguas óptimos pueden solaparse.

Entrada

• Línea 1: enteros $N$, $M$ separados por espacios.
• Líneas $2..N+1$: línea $i+1$, un entero $X_{i}$.
• Líneas $N+2..N+M+1$: línea $N+j+1$, un entero $C_{j}$.

Salida

• Línea 1: entero del coste mínimo para todas las vacas.

Ejemplos

Entrada 1

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

Salida 1

9

Nota

Hay 12 establos, ocupados en 1, 2, 4, 8, 11, 12. Cubrir uno cuesta 2, dos 3, y así sucesivamente.

Uno de cada ancho 4, 1, 2 cubre todas por $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$ representa vaca, $U$ parte del paraguas.

Autor del problema: Alex Chen, 2011