Để tạo không khí vui tươi cho kỳ thi HSG toàn tỉnh, thầy cô các trường quyết định tổ chức hội chợ ẩm thực để các em học sinh được giao lưu với nhau. Ban tổ chức đã xây dựng sẵn ~m~ gian hàng liền nhau đánh số lần lượt ~1, 2, \dots, m~. Tuy nhiên chỉ có ~n~ gian hàng trong số chúng được chọn. Gian hàng thứ ~i~ được chọn có số hiệu ~x[i]~. Không có hai gian hàng được chọn có cùng số hiệu.

Để tiết kiệm chi phí, ban tổ chức chỉ che mưa cho những gian hàng được chọn bằng những tấm bạt. Một tấm bạt phủ được đúng từ gian hàng số hiệu ~u~ đến gian hàng số hiệu ~v~ (~u \le v~) được coi là có kích thước ~v - u + 1~. Giá của một tấm bạt kích thước ~w~ là ~C[w]~. Chú ý rằng những tấm bạt kích thước lớn hơn không nhất thiết phải đắt hơn những tấm bạt kích thước nhỏ hơn.

Yêu cầu: Hãy giúp ban tổ chức tính số tiền ít nhất để có thể mua bạt che tất cả các gian hàng được chọn. Chú ý rằng trong phương án tối ưu các tấm bạt có thể phủ chồng lên nhau ở một số gian hàng.

Input

• Dòng đầu chứa 2 số nguyên dương ~n, m~ (~n \le 5000; 1 \le m \le 10^5~).
• Dòng thứ 2 chứa ~n~ số nguyên dương ~x[1], x[2], \dots, x[n]~ (~x[i] \le m~ với mọi ~i~).
• Dòng thứ 3 chứa ~m~ số nguyên dương ~C[1], C[2], \dots, C[m]~ (~C[i] \le 10^6~).

Output

• Một số là chi phí nhỏ nhất tìm được.

Sample Input 1

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

Sample Output 1

9