Trong một buổi tập bắn súng, có ~N~ tấm bia được xếp thành một hàng dọc, đánh số từ 1 tới ~N~. Độ bền của các tấm bia được mô tả bởi dãy số ~A~, tấm bia thứ ~i~ có độ bền ban đầu là ~A_i~.

Một tấm bia được coi là bị phá hủy nếu độ bền của nó giảm xuống nhỏ hơn hoặc bằng ~0~ (khi này coi độ bền của tấm bia là ~0~).

Xạ thủ được quyền chọn một loại đạn có sức công phá ~X~ (với ~X~ là số nguyên dương tùy ý) để sử dụng cho toàn bộ buổi tập. Mỗi lần bắn, xạ thủ bắn một viên đạn thẳng dọc theo hàng các tấm bia, viên đạn sẽ trúng tấm bia đầu tiên chưa bị phá hủy (tấm bia thứ ~i~ có chỉ số nhỏ nhất và độ bền ~A_i > 0~).

Do đạn có tính xuyên phá nên sẽ gây ảnh hưởng lên tấm bia thứ ~i~ và các tấm bia thứ ~j~ phía sau nó (~j ≥ i~). Độ bền của tấm bia thứ ~j~ (~i ≤ j ≤ N~) bị giảm một lượng theo công thức: ~max(0, X - (j - i)^2)~.

Ví dụ: với ~X = 5~, có 6 tấm bia với độ bền lần lượt là ~[0, 2, 5, 0, 1, 2]~, viên đạn đầu tiên trúng vào tấm bia thứ ~2~, sẽ gây ảnh hưởng cho các tấm bia thứ ~2, 3, 5, 6~ (vì tấm bia 1 và 4 có độ bền bằng 0), độ bền của các tấm bia bị giảm được tính như sau:

• Tấm bia thứ ~2~: ~max(0, 5 - (2 - 2)^2) = max(0, 5 - 0^2) = 5~.
• Tấm bia thứ ~3~: ~max(0, 5 - (3 - 2)^2) = max(0, 5 - 1^2) = 4~.
• Tấm bia thứ ~5~: ~max(0, 5 - (5 - 2)^2) = max(0, 5 - 3^2) = 0~.
• Tấm bia thứ ~6~: ~max(0, 5 - (6 - 2)^2) = max(0, 5 - 4^2) = 0~.

Vậy sau lượt bắn này, độ bền của các tấm bia là ~[0, 0, 1, 0, 1, 2]~.

Yêu cầu: Hãy tìm giá trị sức công phá ~X~ nhỏ nhất sao cho xạ thủ có thể phá hủy toàn bộ các tấm bia khi bắn không quá ~K~ lần.

Input

• Dòng đầu chứa hai số nguyên dương ~N~, ~K~ (~N ≤ 2 × 10^5~; ~K ≤ 10^9~) tương ứng là số tấm bia và số lần bắn tối đa.
• Dòng tiếp theo chứa ~N~ số nguyên dương mô tả dãy ~A~ (~A_i ≤ 10^9~; ~1 ≤ i ≤ N~).

Output

Gồm một số nguyên dương ~X~ nhỏ nhất tìm được.

Sample Input 1

6 3
6 7 1 3 2 1

Sample Output 1

5

Sample Input 2

3 1
3 7 3

Sample Output 2

8

Subtasks

• Có 30% số test ứng với 30% số điểm có ~N, K ≤ 30~; ~A_i ≤ 30~.
• 20% số test tiếp theo ứng với 20% số điểm có ~K = 1~.
• 30% số test tiếp theo ứng với 30% số điểm có ~N ≤ 1000~.
• 20% số test còn lại với 20% số điểm không có ràng buộc gì thêm.