Chạy Bộ
Xem PDFHôm nay là một ngày Chủ Nhật đẹp trời, quyết định sẽ đi tập chạy quanh thành phố của mình để tăng cường sức khỏe sau \(7749\) ngày ngồi gõ code.
Thành phố nơi Thanh Nguyên sống có \(n\) cửa hàng bán đồ gia dụng, được đánh số từ \(1\) tới \(n\). quyết định sẽ chạy bộ từ cửa hàng thứ \(1\) tới cửa hàng thứ \(n\) và sẽ mua các vật phẩm trong các cửa hàng. Cửa hàng thứ \(i\) có bán loại vật phẩm thứ \(a_{i}\) với giá tiền \(c_{i}\) (các cửa hàng khác nhau có thể bán cùng một loại vật phẩm). Trên đường chạy của mình, cần mua \(m\) vật phẩm. Tại mỗi cửa hàng, cậu ấy quyết định sẽ mua vật phẩm đó hay không, nếu không thì cậu ấy sẽ bỏ qua cửa hàng đó và không thể mua vật phẩm ở cửa hàng đó nữa.
Hỏi số tiền ít nhất mà cần chi để mua đủ các vật phẩm theo yêu cầu là bao nhiêu?
Input
- Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n,m \le 10^6, m \le n\)).
- \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(a_{i}\) và \(c_{i}\) (\(a_{i} \le n, c_{i} \le 10^9\)).
- Dòng thứ \(n+1\) chứa \(m\) số nguyên, là các vật phẩm cần mua. Các số có thể trùng nhau.
Output
- In ra một số nguyên duy nhất là số tiền ít nhất phải chi. Nếu không mua được theo yêu cầu thì ghi ra số nguyên
-1.
Example
Test 1
Input
6 4
1 2
1 3
1 4
1 5
2 2
2 3
1 1 2 1Output
11
Bình luận
ai có thể giải thích lại cái đề được ko ạ?
mình ko hiểu 😵
-
0
tnhngoc26
4:26 p.m. 8 Tháng 8, 2023
1 bình luận nữamìn xin phép được sưng là mìn nhé mìn nghĩ đề là ở dòng thứ n+1 bạn có m ptu là các vật phẩm cần thiết và bạn pải mua tất cả m vật phẩm đó với giá tiền ít nhất vd như là ở đây ở dòng số n+1 có m vật phẩm là 1 1 2 1 thì bạn mua các vật phẩm 1 ở các cửa hàng bán vật phầm 1 với giá ci thấp nhất và các vật phẩm 2 cũng tương tự như vậy ở đây thì có 3 cửa hàng có giá bàn vật phẩm 1 vs giá ci thấp nhất là cửa hàng thứ 1 2 3 tương ứng với giá ci là 2 3 4 và 1 cửa hàng bán vật phẩm 2 vs giá ci thấp nhất là cửa hàng thứ 5 vs giá ci là 2 và bạn cộng tổng giá ci của các cửa hàng bán các vật phẩm trên vs giá thấp nhất lại là 2+3+4+2=11