Mua hàng

Điểm: 6,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

24-25 HSG9 HANOI

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

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 \leq A_{i} \leq 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 \leq M \leq N \leq 10^{5}$ ).
Dòng thứ hai gồm $N$ số nguyên dương $A_{1}, A_{2}, . . ., A_{N}$ ( $1 \leq A_{i} \leq M$ ; $1 \leq i \leq 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 \leq T_{i} \leq 10^{9}$ ; $1 \leq i \leq 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 \leq M \leq N \leq 10^{5}$
$1 \leq A_{i} \leq M$
$1 \leq T_{i} \leq 10^{9}$
10% số test: $M = 1$
30% số test: $M = N$
30% số test: $N \leq 2000$
30% số test: không có ràng buộc gì thêm.

Ví dụ

Input	Output	Giải thích
5 2 1 2 1 1 2 5 10 6 8 3	11	Cách mua sao cho tổng số phút nhỏ nhất: 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$ .

Bình luận

Không có bình luận tại thời điểm này.