Piove! Le $N$ mucche di Farmer John ($1 \le N \le 5,000$), numerate $1..N$, non vogliono bagnarsi. Box senza tetto sulla retta hanno coordinate $X$ da 1 a $M$ ($1 \le M \le 100,000$). Mucca $i$ è in $X_{i}$ ($1 \le X_{i} \le M$); nessuna condivide box.

Vuole ombrelli. Da $X_{i}$ a $X_{j}$ ($X_{i} \le X_{j}$), larghezza è $X_{j} - X_{i} + 1$. Larghezza $W$ costa $C_W$ ($1 \le C_{W} \le 1,000,000$). I grandi non costano necessariamente di più.

Trova il costo minimo di un insieme che protegga tutte. Gli ombrelli ottimi possono sovrapporsi.

Input

• Riga 1: interi $N$, $M$ separati da spazi.
• Righe $2..N+1$: riga $i+1$, un intero $X_{i}$.
• Righe $N+2..N+M+1$: riga $N+j+1$, un intero $C_{j}$.

Output

• Riga 1: intero del costo minimo per tutte le mucche.

Esempi

Input 1

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

Output 1

9

Spiegazione

Ci sono 12 box, occupati in 1, 2, 4, 8, 11, 12. Coprirne uno costa 2, due 3, e così via.

Uno di ciascuna larghezza 4, 1, 2 copre tutte per $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$ indica mucca, $U$ parte di ombrello.

Autore del problema: Alex Chen, 2011