TRIP455 Chuyến đi

TRIP455 Chuyến đi

Giáo sư X tổ chức cho 𝑛 học sinh của mình đi làm tình nguyện tại hành tinh Alpha. Các học sinh được đánh số từ 1 tới 𝑛, mỗi học sinh sẽ tới trường và lên tàu vũ trụ bay tới hành tinh Alpha.

Số lượng tàu cũng như số lượng học sinh lên mỗi tàu là không hạn chế, tuy nhiên vì việc phóng tàu vũ trụ khá phức tạp nên hai lần phóng tàu liên tiếp phải cách nhau đúng Δ giây.

Khi một con tàu được phóng, tất cả các học sinh đã đến trường trước hoặc bằng thời điểm phóng tàu sẽ lên tàu và đi luôn. Những học sinh đến sau thời điểm phóng tàu sẽ phải đợi chuyến tàu kế tiếp (cách Δ giây so với chuyến tàu vừa phóng).

Yêu cầu: Cho biết thời điểm mỗi học sinh đến trường, hãy giúp giáo sư X xác định thời điểm phóng con tàu đầu tiên để tổng thời gian chờ đợi của các học sinh là nhỏ nhất.

Input

·        Dòng 1 chứa hai số nguyên dương 𝑛, Δ cách nhau bởi dấu cách (𝑛 ≤ 10⁵; Δ ≤ 10⁹)

·        Dòng 2 chứa 𝑛 số nguyên cách nhau bởi dấu cách lần lượt là thời điểm 𝑛 học sinh tới trường, các thời điểm này là số nguyên không âm và không quá 10⁹ .

Output: một số nguyên duy nhất là tổng thời gian chờ đợi (tính bằng giây) của 𝑛 học sinh.

Input	Output
5 4 9 3 7 6 11	3

Giải thích phương án tối ưu: Tàu đầu tiên phóng vào thời điểm 3, dãy các thời điểm phóng tàu là 3, 7, 11, 15, ….

·        HS 1 đợi 2 giây lên chuyến 3.

·        HS 2 đợi 0 giây lên chuyến 1

·        HS 3 đợi 0 giây lên chuyến 2

·        HS 4 đợi 1 giây lên chuyến 2

HS 5 đợi 0 giây lên chuyến 3