Che Ô

Có $N$ vị trí trên trục số cần được che. Một chiếc ô có độ rộng $W$ (che từ $x$ đến $x+W-1$) có giá $C_W$. Các ô có thể chồng lấp.

Hãy tìm chi phí tối thiểu để mua các ô che phủ tất cả $N$ vị trí.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $M$ ($M$ là tọa độ lớn nhất)
• $N$ dòng tiếp theo: Tọa độ mỗi vị trí cần che
• $M$ dòng tiếp theo: $C_1,C_2,\dots ,C_M$ — giá ô có độ rộng $1,2,\dots ,M$

Dữ liệu ra

• In ra chi phí tối thiểu.

Ràng buộc

• $1\le N\le 5000$
• $1\le M\le 100000$
• $1\le C_i\le {10}^9$

Ví dụ