Problem
Tom Sawyer thuyết phục n bạn bè của mình giúp anh ta trong nhiệm vụ khó khăn là sơn hàng rào bao quanh nhà dì Polly. Hàng rào bao gồm k tấm ván nối tiếp nhau, được đánh số từ 1 đến k, cứ sau tấm ván thứ k lại đến tấm ván đầu tiên.
Bạn của Tom rất khó tính, bạn thứ i chỉ đồng ý tham gia vẽ tranh nếu được phép vẽ đúng một đoạn của các tấm ván liên tiếp. Tom chỉ có một bàn chải, vì vậy những người bạn của anh ấy sẽ lần lượt vẽ và ngay lập tức toàn bộ phân khúc được giao cho họ. Việc duy nhất Tom phải làm là chọn thứ tự mời bạn bè của mình, cũng như chọn số lượng bảng liên tiếp mong muốn cho mỗi người.
Đồng thời, mỗi người bạn của Tom đều sẵn sàng sơn cả một tấm bảng hàng rào chưa sơn và một tấm bảng đã được sơn bởi một trong những người tiền nhiệm của anh ấy. Tuy nhiên, bạn bè sẽ thích thú hơn khi sơn một tấm bảng không sơn. Tom muốn chọn một số x và phân phối các phần hàng rào được sơn sao cho mỗi người bạn của anh ấy sơn ít nhất x tấm ván chưa sơn. Tom rất yêu quý bạn bè của mình và muốn mỗi người trong số họ đạt được kết quả tốt nhất khi sơn hàng rào, vì vậy anh ấy cố gắng tối đa hóa x.
Hãy giúp Tom hiểu rằng anh ấy có thể mang đến cho bạn bè bao nhiêu niềm vui.
Định dạng dữ liệu đầu vào
Dòng đầu tiên của tệp đầu vào chứa hai số nguyên n (1 ≤ n ≤ 10
5 ) và k (1 ≤ k ≤ 10
9 ). Dòng tiếp theo chứa n số nguyên — giá trị a
i (1 ≤ a
i ≤ k).
Định dạng dữ liệu đầu ra
In một số — giá trị tối đa có thể có của
x.
| Đầu vào |
Đầu ra |
2 100
5 10
| 5 |
4 10
7 8 3 5
| 2 |
Giải thích
Trong ví dụ đầu tiên x = 5 vì một trong những người bạn không muốn vẽ nhiều hơn năm bảng. Anh ấy sẽ đến trước, vẽ năm bảng của mình, sau đó 10 bảng không sơn khác sẽ đến tay người bạn thứ hai của Tom. 85 bảng còn lại sẽ phải do chính Tom vẽ.
Trong ví dụ thứ hai, x = 2 có thể đạt được, chẳng hạn như thế này. Đầu tiên, bạn thứ ba tô các bảng từ 4 đến 6 (3 bảng chưa tô). Sau đó bạn thứ tư tô các bảng từ 1 đến 5 (3 bảng chưa tô). Sau đó bạn thứ hai tô các bảng từ 1 đến 8 (2 bảng không tô). Cuối cùng, bạn thứ nhất sơn các bảng từ 6 đến 10 và 1 đến 2 (2 bảng không sơn, lưu ý rằng hàng rào đi theo chu kỳ và các bảng này tạo thành một đoạn liên tiếp).