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ó \((i ≤ j ≤ N)\). Độ bền của tấm bia thứ \(j\) bị giảm một lượng theo công thức: \(max(0, X - (j - i)^2)\).

Input

• Dòng đầu chứa hai số nguyên dương \(N, K\) (\(N \leq 2\cdot 10^5; K \leq 10^5\)) 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 \leq 10^9; 1 \leq i \leq N\)).

Output

• In ra một số nguyên dương \(X\) nhỏ nhất tìm được.

Example

6 3
6 7 1 3 2 1

5

3 1
3 7 3

8

Scoring

• \(30\%\) số test ứng với \(30\%\) số điểm có \(N, K \leq 30; A_i \leq 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 \leq 1000\)
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm