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.

Yêu cầu

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 đầu vào

Gồm ~Q + 1~ dòng:

• 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 đầu ra

Gồm 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 dữ liệu

• Có 10% số test ứng với 10% số điểm của bài thoả mãn: ~M = 1~;
• 30% số test khác ứng với 30% số điểm của bài thoả mãn: ~M = N~;
• 30% số test khác ứng với 30% số điểm của bài thoả mãn: ~N \le 2000~;
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5 2
1 2 1 1 2
5 10 6 8 3

OUTPUT

11

Giải thích: Cách mua sao cho tổng số phút nhỏ nhất là:

• Mua sản phẩm ~1~ ở quầy hàng thứ ~3~ mất ~6~ phút;
• Di chuyển sang quầy hàng thứ ~5~ mất ~2~ phút;
• Mua sản phẩm ~2~ ở quầy hàng thứ ~5~ mất ~3~ phút;

Tổng số phút là: ~6 + 2 + 3 = 11~.