Câu 3. RÓT NƯỚC (2.5 điểm)

Cho \(N\) thùng đựng nước đặt cố định liên tiếp nhau, được đánh số từ 1 đến \(N\). Thùng thứ \(i\) có dung tích là \(A_i\) lít. Ban đầu, các thùng đều rỗng và tại mỗi thùng đều có một vòi nước rót vào với lưu lượng giống nhau là \(K\) lít/giây. Khi thùng thứ \(i\) đầy nước (\(1 \leq i < N\)) thì các vòi đang rót vào thùng \(i\) được chuyển qua rót vào thùng thứ \(i + 1\). Khi thùng thứ \(N\) đầy nước thì nước sẽ chảy ra ngoài.

Input

Vào từ tệp văn bản WATERFILL.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương \(N\) và \(K\). (\(1 \leq N \leq 10^5\); \(1 \leq K \leq 10^9\)).
• Dòng tiếp theo chứa \(N\) số nguyên \(A_1, A_2, ..., A_N\). Các số được ghi cách nhau một ký tự trắng. (\(1 \leq A_i \leq 10^9\), với mọi \(1 \leq i \leq N\)).

Output

Ghi ra tệp văn bản WATERFILL.OUT một số nguyên duy nhất là thời gian sớm nhất để tất cả các thùng đều đầy nước (đơn vị tính bằng giây).

Example

4 2
1 2 15 14

4

4 3
10 14 3 22

5