Hải Dương tổ chức hội chợ nông sản. Dọc đại lộ Tôn Đức Thắng, ban tổ chức đã xây dựng \(m\) gian hàng liền nhau đánh số lần lượt \(1\), \(2\), ..., \(m\). Tuy nhiên chỉ có \(n\) gian hàng trong số chúng được thuê. Gian hàng thứ \(i\) được thuê có số hiệu \(x_i\). Không có hai gian hàng được thuê 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 thuê bằng những tấm bạt. Một tấm bạt phủ được từ gian hàng số hiệu \(u\) đến gian hàng số hiệu \(v\) (\(u\) \(\leq\) \(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.

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 thuê. 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 ghi hai số nguyên dương \(n\), \(m\) (_\(1 \leq n \leq 5000, 1 \leq m \leq 10^5\))
• Dòng thứ hai chứa \(n\) số nguyên dương \(x_1, x_2,...,x_n\) (\(1 \leq x_i \leq m, x_i ≠ x_j, ∀ i ≠ j\))
• Dòng thứ ba chứa \(m\) số nguyên \(C_1, C_2,…,C_m (1 \leq C_i \leq 10^6\)) là giá của những tấm bạt kích thước \(1, 2,...,m\)

Các số liên tiếp trên cùng một dòng của file dữ liệu vào cách nhau ít nhất một dấu cách.

Output:

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

Ví dụ:

input

6 12

1 2 11 8 4 12

2 3 4 4 8 9 15 16 17 18 19

19

9

Hình minh họa ví dụ

Có 12 gian hàng, các gian màu xám là các gian được thuê. Ở trên sử dụng ba tấm bạt kích thước 4, 1 và 2