(7 ĐIỂM)CÓ M ĐOÀN HỌC SINH CỦA CÁC TRƯỜNG ĐẾN THAM DỰ KÌ THI THT2013....

Bài 3: (7 điểm)

Có M đoàn học sinh của các trường đến tham dự kì thi THT2013. Các trưởng đoàn đang

xếp hàng tại khu vực nhà chờ để chờ đến lượt làm thủ tục đăng kí dự thi cho đoàn của trường

mình. Có N bàn làm thủ tục đăng kí dự thi tại khu vực tiếp tân. Nhân viên tại bàn thứ k mất T

k

giây để hoàn thành thủ tục đăng kí cho một đoàn bất kì. Bắt đầu giờ làm việc (tại thời điểm 0),

tất cả các bàn đều có nhân viên trực sẵn sàng làm thủ tục và các trưởng đoàn đã xếp thành một

hàng dọc tại khu vực nhà chờ. Một người chỉ có thể đến một bàn đang rỗi để làm thủ tục khi tất

cả người phía trước mình trong hàng đợi đã rời khỏi hàng (có thể đang làm thủ tục ở một bàn nào

đó hoặc đã làm xong thủ tục). Người ở đầu hàng đợi có thể chọn đến làm thủ tục tại một trong

các bàn đang rỗi hoặc chờ một bàn đang bận cho đến khi nó rỗi.

Tổng thời gian hoàn thành việc đăng kí cho tất cả các đoàn chính là khoảng thời gian từ

thời điểm bắt đầu làm việc đến thời điểm trưởng đoàn cuối cùng làm xong thủ tục dự thi. Thật

tuyệt vời là tất cả các trưởng đoàn đều là những chuyên gia tin học, vì vậy họ đều chọn đến làm

thủ tục tại những bàn sao cho thời gian hoàn thành đăng kí dự thi cho tất cả các đoàn là ít nhất.

Nhiệm vụ của bạn là giúp ban tổ chức tìm ra tổng thời gian ít nhất này (có thể xem thời

gian di chuyển từ nhà chờ đến khu vực tiếp tân không đáng kể).

Ví dụ: Có 6 đoàn và 2 bàn đăng kí dự thi với thời gian xử lí công việc là 7 giây và 10 giây.

Tại thời điểm 0, hai trưởng đoàn đến đăng kí tại hai bàn.

Tại thời điểm 7, bàn thứ nhất rỗi và trưởng đoàn thứ 3 đến làm thủ tục tại bàn này.

Tại thời điểm 10, trưởng đoàn thứ 4 đến bàn thứ hai.

Tại thời điểm 14, trưởng đoàn thứ 5 đến làm thủ tục tại bàn thứ nhất.

Tại thời điểm 20, bàn thứ 2 rỗi, nhưng trưởng đoàn thứ 6 quyết định chờ đến thời điểm

21, đến bàn thứ nhất làm thủ tục.

Theo cách này, thời gian hoàn thành thủ tục đăng kí cho tất cả các đoàn là 28 giây (Nếu

trưởng đoàn thứ 6 không chờ mà quyết định đến bàn thứ nhất ở thời điểm 20 thì thời gian hoàn

thành thủ tục đăng kí cho tất cả các đoàn là 30 giây).

Dữ liệu vào: Cho trong file văn bản MOMENT.IN gồm N+1 dòng:

 Dòng đầu tiên chứa 2 số nguyên dương N (1≤ N ≤ 100 000) – số bàn làm thủ tục đăng kí

và M (1≤M≤1 000 000 000)- số đoàn tham dự kì thi.

 N dòng tiếp theo, mỗi dòng gồm một số nguyên dương T

k

– thời gian hoàn thành thủ tục

đăng kí cho một đoàn học sinh của từng bàn (1 ≤ T

k

≤ 10

⁹

, các số được viết cách nhau ít

nhất một dấu cách.)

Dữ liệu ra: Ghi ra màn hình một số nguyên duy nhất, là thời gian (tính bằng giây) ít nhất hoàn

thành việc đăng kí cho tất cả các đoàn.

Ví dụ 1: Ví dụ 2:

Dữ liệu vào

2 6

7 10

3

7

10

8

6

9

2

4

Dữ liệu ra

28