Trong ngôi làng nhỏ, có một người nông dân tên là Bình. Bình là một người nông dân có tâm hồn đam mê trồng trọt. Anh muốn đào đất xuống sâu nhất có thể để cây dễ dàng lấy chất dinh dưỡng từ vùng đất sâu. Một ngày nọ, trong lúc làm ruộng, anh phát hiện ra rằng các thửa đất sát nhau có độ cao chênh lệch không quá 1 đơn vị. Vì để dễ trồng, trong quá trình đào đất, anh ta vẫn muốn giữ đúng kết cấu của ruộng (2 thửa đất sát nhau có độ cao chênh lệch không quá 1 đơn vị). Mỗi lần Bình đào một thửa đất xuống 1 đơn vị độ cao thì anh tiêu hao 1 đơn vị sức lực. Khi sử dụng hết sức lực thì anh không thể đào tiếp được nữa. Vậy hỏi, trong ngày hôm nay với M sức lực, Bình có thể đào sâu nhất là bao nhiêu?

Độ cao các thửa đất được biểu thị bởi N số trên một dòng. Hai số liên tiếp có giá trị chênh lệch nhau không quá 1 đơn vị (|hi - hi - 1| ≤ 1 với 2 ≤ i ≤ N và hi là độ cao thửa đất thứ i).

Yêu cầu: Hãy giúp Bình tìm xem với M đơn vị sức lực thì Bình sẽ đào được sâu nhất là bao nhiêu mà vẫn thỏa mãn yêu cầu trên.

Dữ liệu: Vào từ file văn bản FARMER.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương N, M (N ≤ 10^5, M ≤ 10^12) là số thửa đất trên mảnh ruộng và sức lực của Bình trong ngày hôm nay.

• Dòng tiếp theo chứa N số nguyên dương với hi là độ cao thửa đất thứ i (1 ≤ hi ≤ 10^5).

Kết quả: Đưa ra file văn bản FARMER.OUT một số nguyên duy nhất là độ sâu sâu nhất mà Bình có thể đào được.

Ví dụ:

Input

4 3
1 1 1 1

Output

-1

Ví dụ 2:

Input

4 3
1 2 2 1

Output

0

Ràng buộc:

• Subtask 1 (25% số điểm): N, M ≤ 10^3
• Subtask 2 (25% số điểm): N ≤ 10^3, M ≤ 10^8
• Subtask 3 (25% số điểm): N ≤ 10^5, M ≤ 10^12, h1 = h2 = ... = hN
• Subtask 4 (25% số điểm): Không có ràng buộc gì thêm.

Bản PDF