소를 위한 우산

비가 오는 날입니다. 농부 John의 소 $N$마리($1 \le N \le 5{,}000$)는 $1 \ldots N$로 번호가 매겨져 있으며, 비를 맞는 것을 좋아하지 않습니다. 소들은 수직선 위에 늘어선 지붕 없는 축사에 서 있습니다. 축사는 좌표 $1$부터 $M$까지($1 \le M \le 100{,}000$)의 정수 좌표를 차지합니다. 소 $i$는 좌표 $X_i$($1 \le X_i \le M$)에 서 있으며, 두 소가 같은 축사를 공유하지 않습니다.

소들이 비에 젖지 않도록 농부 John은 우산을 사려고 합니다. 좌표 $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$)입니다. 더 넓은 우산이 반드시 더 비싼 것은 아닙니다.

모든 소를 비로부터 보호하는 우산 집합의 최소 총비용을 구하세요. 최적해에서 우산들은 서로 겹칠 수 있습니다.

• 첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어집니다.
• 다음 $N$개의 줄에는 각각 정수 $X_i$가 하나씩 주어집니다.
• 그다음 $M$개의 줄에는 각각 정수가 하나씩 주어지며, 그중 $j$번째 줄은 너비가 $j$인 우산의 가격 $C_j$입니다.

• 모든 소가 비에 젖지 않도록 우산을 사는 데 필요한 최소 비용을 정수 하나로 출력합니다.

축사는 $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는 우산의 일부를 나타냅니다.