Chuẩn hóa nhãn (Label Normalization)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ bản ghi theo thứ tự $1,2,\ldots,N$. Bản ghi thứ $i$ đang mang nhãn $A_i$, với $1\le A_i\le M$.

Bạn được phép đổi nhãn của bản ghi $i$ thành một giá trị bất kỳ trong $\{1,2,\ldots,M\}$. Nếu nhãn mới khác $A_i$ thì phải trả chi phí $C_i$; nếu giữ nguyên nhãn thì chi phí bằng $0$.

Sau khi hiệu chỉnh, gọi nhãn mới là $B_1,B_2,\ldots,B_N$. Dãy nhãn phải không giảm:

Hãy tìm tổng chi phí nhỏ nhất để thu được một dãy nhãn không giảm.

Input

• Dòng đầu chứa hai số nguyên $N,M$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.
• Dòng thứ ba chứa $N$ số nguyên $C_1,C_2,\ldots,C_N$.

Output

In một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Subtask

• Subtask 1 — 30%: $1\le N\le 20$, $1\le M\le 5$, $1\le A_i\le M$, $0\le C_i\le 10^9$.
• Subtask 2 — 30%: $1\le N\le 2000$, $1\le M\le 60$, $1\le A_i\le M$, $0\le C_i\le 10^9$.
• Subtask 3 — 40%: $1\le N\le 2\cdot 10^5$, $1\le M\le 60$, $1\le A_i\le M$, $0\le C_i\le 10^9$.

Ví dụ

Ví dụ 1

Input

5 3
3 1 2 1 3
5 2 4 1 3

Output

6

Giải thích

Có thể đổi dãy thành $1,1,2,2,3$. Ta đổi bản ghi $1$ với chi phí $5$ và bản ghi $4$ với chi phí $1$.

Ví dụ 2

Input

4 4
1 2 2 4
8 7 6 5

Output

0

Giải thích

Dãy nhãn ban đầu đã không giảm.