Mua hàng

An đi mua $M$ sản phẩm khác nhau, các sản phẩm được đánh số từ $1$ đến $M$. Ở chợ có $N$ quầy hàng xếp thành hàng ngang được đánh số từ $1$ đến $N$, từ trái sang phải. Quầy hàng thứ $i$ chỉ bán một loại sản phẩm duy nhất là $A_i$ ($1\le A_i\le M$) và với mỗi sản phẩm trong $M$ sản phẩm luôn tồn tại ít nhất một quầy hàng bán sản phẩm loại đó. Thời gian để An mua sản phẩm tại quầy hàng thứ $i$ là $T_i$ phút. Thời gian để di chuyển giữa hai quầy hàng liền kề là $1$ phút.

Tìm cách mua hàng sao cho:

• Mua đủ $M$ sản phẩm theo đúng thứ tự $1,2,3,...,M$. Có thể bắt đầu từ một quầy hàng bất kì bán sản phẩm $1$;
• Thời gian tính từ lúc bắt đầu mua sản phẩm $1$ đến khi mua xong sản phẩm $M$ là nhỏ nhất;

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương $N$, $M$ ($1\le M\le N\le {10}^5$).
• Dòng thứ hai gồm $N$ số nguyên dương $A_1,A_2,...,A_N$ ($1\le A_i\le M$; $1\le i\le N$). Dữ liệu đảm bảo các số từ $1$ đến $M$ xuất hiện ít nhất một lần.
• Dòng thứ ba gồm $N$ số nguyên dương $T_1,T_2,...,T_N$ ($1\le T_i\le {10}^9$; $1\le i\le N$).

Dữ liệu ra

Một số nguyên duy nhất là số phút nhỏ nhất để An mua $M$ sản phẩm theo yêu cầu đề bài.

Ràng buộc

• $1\le M\le N\le {10}^5$
• $1\le A_i\le M$
• $1\le T_i\le {10}^9$
• 10% số test: $M=1$
• 30% số test: $M=N$
• 30% số test: $N\le 2000$
• 30% số test: không có ràng buộc gì thêm.

Ví dụ