| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P145SUMG - ROUND 5G - Điểm kiểm soát sân bay |
Tại sân bay Nội Bài, một hành 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 T_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 (xem ví dụ 1).
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 (N <= 10^5, M <= 10^9). N dòng tiếp theo, mỗi dòng là số nguyên T_i (1 <= T_i <= 10^9).
Output
In ra đáp số của bài toán.
Example
Test 1:
Input:
2 6
7
10
Output:
28
Giải thích test 1: Có 2 trạm kiểm soát và 6 hành khách.
Tại t = 0, hành khách 1 và 2 bước vào trạm kiểm tra I và II. Tại t = 7, trạm I trống, và người thứ 3 được phép đi. Tại t = 10, trạm II trống, người thứ 4 bước vào kiểm tra. Tại t = 14, trạm I trống, người thứ 5 tới kiểm tra. Tại t = 20, trạm II trống, nhưng hành khách thứ 6 sẽ đợi thêm một chút, tới t = 21, trạm I trống và hành khách này sẽ tới kiểm tra, tổng chi phí thời gian bằng 28(s).
Test 2:
Input:
7 10
3
8
3
6
9
2
4
Output:
8
| Được gửi lên bởi: | adm |
| Ngày: | 2014-07-22 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
