GukiZ và những chồng hộp

Có $n$ chồng hộp được xếp thành một hàng từ trái sang phải. Chồng thứ $i$ chứa $a_i$ hộp. Cần dọn sạch tất cả các hộp bằng $m$ học sinh làm việc đồng thời.

Tại thời điểm $0$, tất cả học sinh đứng ngay bên trái chồng đầu tiên. Mỗi học sinh mất đúng $1$ giây để di chuyển từ vị trí ban đầu đến chồng số $1$. Sau đó, ở mỗi giây kế tiếp, mỗi học sinh có thể thực hiện một trong hai thao tác (mỗi thao tác mất đúng $1$ giây):

1. Nếu đang ở chồng $i$ và $i\ne n$, di chuyển sang chồng $i+1$.
2. Nếu chồng hiện tại còn hộp, lấy đi $1$ hộp khỏi chồng đó.

Các học sinh hoạt động hoàn toàn độc lập và có thể cùng đứng trên một chồng. Hãy tìm thời gian tối thiểu $t$ (tính bằng giây) để dọn sạch toàn bộ các hộp. Sau $t$ giây, các học sinh được phép đứng ở vị trí bất kỳ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Một số nguyên duy nhất — thời gian tối thiểu cần thiết để dọn hết các hộp.

Ràng buộc

• $1\le n,m\le {10}^5$
• $0\le a_i\le {10}^9$
• Đảm bảo có ít nhất một chồng khác rỗng.

Ví dụ