우산세트 구매

비가 갑자기 내리고 있습니다! 도시에 사는 N (1 <= N <= 5,000) 명의 1...N까지 번호가 매겨져 있는 시민들은 갑작스런 비에 대비할 우산을 갖고 있지 않습니다. 시민들은 수평선 상에 배치된 지붕이 없는 정류장에 서 있습니다. 정류장은 X좌표 1에서 M(1 <= M <= 100,000)까지를 분포해 있습니다. i 번째 시민은 X_i(1 <= X_i <= M) 좌표에 위치한 정류장에서 서 있습니다. 2명 이상의 시민은 같은 정류장을 공유하지 않습니다.

비로부터 시민들을 보호하기 위해 지나가던 시장은 그들에게 우산을 사주고 싶습니다. 좌표 X_i에서 X_j(X_i <= X_j)까지 아우르는 우산의 폭은 X_j - X_i + 1이다. 폭이 W인 우산을 사기 위해서는 C_W(1 <= C_W <= 1,000,000)의 비용이 듭니다. 큰 우산이 꼭 작은 우산보다 비싸다는 보장은 없습니다.

시장에게 모든 시민들로부터 비를 보호할 수 있는 우산 세트를 구매하는데 필요한 최소 비용을 찾아주십시오. 최적의 해에서 우산 세트가 어느 정도 겹칠 수 있다는 점을 주의하십시오.

• 1번째 줄: 두 개의 띄어쓰기로 구분된 정수: N 및 M.
• 2번째 줄..N+1: i+1번째 줄은 하나의 정수를 포함: X_i.
• N+2번째 줄..N+M+1: N+j+1번째 줄은 하나의 정수를 포함: C_j.

• 1번째 줄: 모든 소를 위한 우산을 구매하는데 필요한 최소 비용입니다.