Phân vùng tre

Có $n$ cây tre trồng thành một hàng. Ngay lúc trồng, mọi cây đều cao $0$ mét và mỗi ngày mỗi cây cao thêm $1$ mét. Cây thứ $i$ cần đạt chiều cao mong muốn là $a_i$ mét.

Ta có thể cắt mỗi cây đúng một lần, tại một độ cao không vượt quá chiều cao hiện tại của nó; sau khi bị cắt, cây ngừng cao thêm.

Việc kiểm tra và cắt chỉ được thực hiện sau mỗi $d$ ngày: tức là sau $d$ ngày, $2d$ ngày, $3d$ ngày, … Vào mỗi lần kiểm tra, ta cắt những cây đã đạt hoặc vượt chiều cao mong muốn, cắt đúng tại độ cao mong muốn $a_i$. Nói cách khác, cây $i$ bị cắt vào lần kiểm tra sớm nhất mà chiều cao của nó $\ge a_i$; khi đó phần thừa phải bỏ đi có độ dài bằng (chiều cao lúc cắt) $-a_i$.

Hãy tìm giá trị $d$ lớn nhất sao cho tổng độ dài các phần tre bị cắt bỏ không vượt quá $k$ mét.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$ — số cây tre và tổng độ dài tối đa cho phép của các phần cắt bỏ.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — chiều cao mong muốn của từng cây.

Dữ liệu ra

In ra một số nguyên duy nhất — giá trị lớn nhất của $d$.

Ràng buộc

• $1\le n\le 100$
• $1\le k\le {10}^{11}$
• $1\le a_i\le {10}^9$

Ví dụ