Hôm nay trời mưa! \(N\) (\(1 \le N \le 5\,000\)) chú bò của Nông dân John, được đánh số từ \(1\) đến \(N\), đặc biệt không thích bị ướt. Những chú bò đang đứng trong các ô chuồng không có mái che, được sắp xếp trên một trục số. Các ô chuồng có tọa độ \(X\) từ \(1\) đến \(M\) (\(1 \le M \le 100\,000\)). Chú bò \(i\) đứng trong ô chuồng tại tọa độ \(X_i\) (\(1 \le X_i \le M\)). Không có hai chú bò nào đứng chung một ô chuồng.

Để bảo vệ đàn bò khỏi mưa, Nông dân John muốn mua ô cho chúng. Một chiếc ô phủ từ tọa độ \(X_i\) đến \(X_j\) (\(X_i \le X_j\)) có chiều rộng \(X_j-X_i+1\). Chi phí để mua một chiếc ô có chiều rộng \(W\) là \(C_W\) (\(1 \le C_W \le 1\,000\,000\)). Ô lớn hơn không nhất thiết đắt hơn ô nhỏ hơn.

Hãy giúp Nông dân John tìm chi phí nhỏ nhất để mua một tập hợp ô che mưa cho mọi chú bò. Lưu ý rằng các chiếc ô trong một phương án tối ưu có thể chồng lấn lên nhau một phần.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách: \(N\) và \(M\).
• \(N\) dòng tiếp theo; dòng thứ \(i\) chứa một số nguyên duy nhất \(X_i\).
• \(M\) dòng tiếp theo; dòng thứ \(j\) chứa một số nguyên duy nhất \(C_j\).

Dữ liệu ra

• Dòng đầu tiên chứa một số nguyên duy nhất là chi phí nhỏ nhất cần thiết để mua ô cho tất cả những chú bò.

Ví dụ

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

9

UUUUUUUUUU           U        UUUU
C  C     C           C        C  C
|--|--|--|--|--|--|--|--|--|--|--|
1  2  3  4  5  6  7  8  9  10 11 12

Nguồn

USACO 2011 December Contest, Silver Division — Umbrellas for Cows

Tác giả đề: Alex Chen, 2011.