Một này Chủ Nhật đẹp trời nọ, p2o2HuaGiaBao đang dẫn đội tuyển rubik tham dự một giải đấu Rubik với phong cách "ao làng" như sau: Có \(n\) bàn thi đấu được xếp thành một hàng ngang, bàn thứ \(i\) có \(a_i\) khối Rubik đang chờ được giải. Đội tuyển của p2o2HuaGiaBao có \(m\) tuyển thủ sẵn sàng tham gia để dọn sạch toàn bộ số Rubik này.
Lúc bắt đầu (giây \(0\)), tất cả tuyển thủ đều đứng ở ngoài cùng bên trái bàn số \(1\). Mỗi giây, mỗi tuyển thủ có thể thực hiện một trong hai thao tác sau:

• Nếu chưa ở bàn cuối (\(i \ne n\)), di chuyển từ bàn \(i\) sang bàn \(i+1\).
• Nếu tại bàn hiện tại vẫn còn khối Rubik, giải xong một khối Rubik tại bàn đó.
  Các tuyển thủ có thể hoạt động song song, nhưng mỗi thao tác đều mất đúng \(1\) giây cho mỗi thao tác. p2o2HuaGiaBao muốn biết thời gian tối thiểu \(t\) (tính theo giây) để toàn bộ Rubik ở các bàn được giải xong.
  Vì anh ta đã lớn tuổi nên muốn các bạn tính giúp.

Input

• Dòng đầu tiên chứa hai số nguyên \(n,m\) (\(1\le n,m\le 10^5\)) – lần lượt số bàn thi đấu và số tuyển thủ.
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) với (\(0\le a_i\le 10^9\)) với \(a_i\) là số lượng khối Rubik trên bàn thứ \(i\) (\(1\le i\le n\))

Output

• In ra một số tự nhiên \(t\in \mathbb{N}\) duy nhất – thời gian tối thiểu (tính theo giây) để dọn sạch tất cả các khối Rubik.

Example

5 3
0 3 2 1 8 

10

Scoring

• Subtask 1 (\(25\)% points): \(1 \le n,m,a_i \le 10\)
• Subtask 2 (\(25\)% points): \(1 \le n \le 10^5, m=1, a_i=10^9\)
• Subtask 3 (\(25\)% points): \(1 \le n,m \le 2000, a_i=10^6\)
• Subtask 4 (\(25\)% points): Không có ràng buộc gì thêm