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≤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. </p>

Yêu cầu: Tìm 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).

Lưu ý: Đưa ra thời gian là số nguyên nhỏ nhất lớn hơn hoặc bằng thời gian tìm được (ví dụ như thời gian sớm nhất để các thùng đều đầy là ~1.33~ giây thì kết quả in ra sẽ là ~2~).

Dữ liệu vào: Cho trong 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~. (Điều kiện: ~1≤N≤ 10^5; 1≤K≤ 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.(Điều kiện: ~1 ≤A_i≤ 10^9~, với mọi ~1≤i≤N~).

Dữ liệu ra: 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.

Ví dụ:

WATERFILL.INP

4 2
1 2 1514

WATERFILL.OUT

4

WATERFILL.INP

4 3
10 14 3 22

WATERFILL.OUT

5