Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

hide comments
2022-08-04 16:43:46
Bsearch
2017-09-02 12:16:40
Chặt nhị phân, 1 đấm AC :))))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.