Điểm kiểm soát sân bay
Xem dạng PDFTại sân bay Đồng Hới, một đoàn khách gồm M người chuẩn bị tham gia chuyến bay. Vì số lượng khách quá lớn nên điểm kiểm soát của sân bay đã được tăng lên thành N điểm. Tại điểm kiểm soát thứ i, cần mất ~A_i~ (s) để có thể kiểm tra xong một người (tính cả thời gian đi bộ từ địa điểm xếp hàng tới điểm kiểm tra này). Các hành khách sắp xếp theo một hàng đợi. Lần lượt từng người vào một. Hành khách ở đầu hàng đợi được phép đi vào một trạm kiểm soát nào đó nếu như trạm kiểm soát đó đang trống. Tuy nhiên, người đó cũng có quyền đứng chờ để đợi một trạm kiểm soát khác trống để đi tới trạm đó, vì có thể giảm thiểu chi phí thời gian cho cả đoàn.
Yêu cầu: Các bạn hãy tính toán xem thời gian nhỏ nhất có thể để đoàn hành khách kiểm tra xong hành lý là bao nhiêu?
Input:
- Dòng đầu tiên gồm 2 số nguyên N và M, lần lượt là số quầy gửi đồ và số vị khách.
- Dòng 2 ghi N số nguyên ~A_1, A_2,...,A_N~ lần lượt là thời gian kiểm tra xong một người của trạm thứ i.
Output:
- In ra đáp số của bài toán.
Example:
Input:
2 6
7 10
Output:
28
Constraints:
~1 \le A_i \le 10^9 ; N \le 10^5, M \le 10^6~
Bình luận
skibidi yes yes no no
skibidi dop dop yes yes