Chove! As $N$ vacas de Farmer John ($1 \le N \le 5,000$), numeradas $1..N$, não querem se molhar. Baias sem teto ficam numa reta com coordenadas $X$ de 1 a $M$ ($1 \le M \le 100,000$). Vaca $i$ está em $X_{i}$ ($1 \le X_{i} \le M$), sem compartilhar baias.

Quer guarda-chuvas. De $X_{i}$ a $X_{j}$ ($X_{i} \le X_{j}$), largura é $X_{j} - X_{i} + 1$. Largura $W$ custa $C_W$ ($1 \le C_{W} \le 1,000,000$). Grandes não custam necessariamente mais.

Ache o custo mínimo de conjunto para proteger todas. Guarda-chuvas ótimos podem se sobrepor.

Entrada

• Linha 1: inteiros $N$, $M$ separados por espaços.
• Linhas $2..N+1$: linha $i+1$, um inteiro $X_{i}$.
• Linhas $N+2..N+M+1$: linha $N+j+1$, um inteiro $C_{j}$.

Saída

• Linha 1: inteiro do custo mínimo para todas as vacas.

Exemplos

Entrada 1

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

Saída 1

9

Nota

Há 12 baias, ocupadas em 1, 2, 4, 8, 11, 12. Cobrir uma custa 2, duas 3, e assim por diante.

Um de cada largura 4, 1, 2 cobre 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 de guarda-chuva.

Autor do problema: Alex Chen, 2011