Сегодня дождь! $N$ коров Farmer John ($1 \le N \le 5,000$), номера $1..N$, не любят мокнуть. Стойла без крыш стоят на прямой с $X$-координатами от 1 до $M$ ($1 \le M \le 100,000$). Корова $i$ в $X_{i}$ ($1 \le X_{i} \le M$), две не делят стойло.

Он покупает зонты. Зонт от $X_{i}$ до $X_{j}$ ($X_{i} \le X_{j}$) имеет ширину $X_{j} - X_{i} + 1$. Ширина $W$ стоит $C_W$ ($1 \le C_{W} \le 1,000,000$). Большие не обязательно дороже малых.

Найдите минимальную стоимость набора для всех коров. В оптимуме зонты могут частично перекрываться.

Входные данные

• Строка 1: целые $N$, $M$ через пробел.
• Строки $2..N+1$: строка $i+1$ содержит целое $X_{i}$.
• Строки $N+2..N+M+1$: строка $N+j+1$ содержит целое $C_{j}$.

Выходные данные

• Строка 1: целое, минимальная стоимость зонтов для всех.

Примеры

Входные данные 1

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

Выходные данные 1

9

Примечание

Есть 12 стойл, коровы в 1, 2, 4, 8, 11, 12. Зонт на одно стоит 2, на два 3, и так далее.

По одному ширины 4, 1, 2 покроют всех за $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$ — корова, $U$ — часть зонта.

Автор задачи: Alex Chen, 2011