TS10 2024 - Quảng Nam - Bài 4 - Thiền nguyện (2 điểm)
Xem dạng PDFSau trận đại dịch Covid-19 năm 2020, nhiều tỉnh thành đã rơi vào hoàn cảnh khốn khó. Với tinh thần đoàn kết tương trợ, doanh nghiệp ~A~ dự định lên kế hoạch sẽ tổ chức đi thiện nguyện đến vùng cao. Địa điểm đầu tiên doanh nghiệp ~A~ dự tính đến là các đồng bào có hoàn cảnh khó khăn thuộc tỉnh Lai Châu.
Trong chuyến đi này, có ~n~ đoàn tham gia, được đánh số từ ~1~ đến ~n~ (~0 < n ≤ 10^6~). Mỗi đoàn sẽ đến thăm và tặng quà cho bà con tại một ngôi làng trong huyện trên địa bàn tỉnh Lai Châu. Trong đó, đoàn thứ ~i~ sẽ di chuyển đến ngôi làng cách thành phố Lai Châu với quãng đường ~d_i~ km (~1 ≤ d_i ≤ 10^6~).
Doanh nghiệp ~A~ mong muốn chuyến đi diễn ra kịp thời, đúng tiến độ nên phải chuẩn bị ~m~ chiếc xe được đánh số từ ~1~ đến ~m~ (~n ≤ m ≤ 10^6~). Các xe được đổ đầy nhiên liệu, xe thứ ~j~ có mức tiêu thụ nhiên liệu ~v_j~ (~1 ≤ v_j ≤ 10^6~) đơn vị thể tích/km.
Yêu cầu: Để quá trình vận chuyển thuận lợi và ít tốn kém cho doanh nghiệp, bộ phận kế toán phải tính thế nào để chọn được ~n~ chiếc xe phục vụ chuyến đi sao cho tổng chi phí nhiên liệu được sử dụng là ít nhất (biết rằng mỗi xe chỉ phục vụ một đoàn).
Input
Dòng đầu tiên ghi hai số nguyên dương ~n, m~ (các số cách nhau một khoảng trắng).
Dòng thứ hai ghi các số nguyên dương ~d_1, d_2, …, d_n~ (các số cách nhau một khoảng trắng).
Dòng thứ ba ghi các số nguyên dương ~v_1, v_2, …, v_m~ (các số cách nhau một khoảng trắng).
Output
Dòng đầu tiên ghi tổng số nhiên liệu cần dùng cho việc đưa các đoàn đi thiện nguyện (chỉ tính lượt đi).
Dòng thứ hai ghi chỉ số xe phục vụ chuyến đi theo thứ tự tăng dần của nhiên liệu bị tiêu tốn (các số cách nhau một khoảng trắng).
Scoring
Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 50, d_i, v_j ≤ 10^2~.
Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 100, d_i, v_j ≤ 10^3~.
Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 10^3, d_i, v_j ≤ 10^6~.
Có 25% test tương ứng 25% số điểm của bài với ~1 ≤ n, m ≤ 10^6, d_i, v_j ≤ 10^6~.
Example
Input
3 4
2 5 9
22 13 23 10
Output
199
4 2 1
Bình luận
ai hieu de ko v :))
co
noi di t no hieu :))