Mô tả bài toán

Bạn có ~ N ~ cây gỗ với chiều cao lần lượt là ~ A[1], A[2], \ldots, A[N] ~. Bạn muốn lấy một lượng gỗ tối thiểu ~ M ~ bằng cách chặt ~ N ~ cây. Với mỗi cây, bạn chỉ lấy phần thừa của cây khi chiều cao cây vượt qua mức cắt ~ H ~.

Yêu cầu: Tìm giá trị lớn nhất của ~ H ~ sao cho tổng lượng gỗ thu được ít nhất là ~ M ~.

Input:

1. Dòng đầu tiên chứa hai số nguyên ~ N ~ và ~ M ~ (~ 1 \leq N \leq 10^6, 1 \leq M \leq 2 \times 10^9 ~).
2. Dòng thứ hai chứa ~ N ~ số nguyên ~ A[1], A[2], \ldots, A[N] ~ (~ 1 \leq A[i] \leq 10^9 ~).

Output:

• In một số nguyên duy nhất là giá trị ~ H ~ lớn nhất.

Ví dụ:

Input:

4 7
20 15 10 17

Output:

15

Giải thích:

1. Với ~ H = 15 ~:
   • Cây 1: ~ 20 - 15 = 5 ~.
   • Cây 2: ~ 15 - 15 = 0 ~.
   • Cây 3: ~ 10 - 15 = 0 ~.
   • Cây 4: ~ 17 - 15 = 2 ~.
   • Tổng: ~ 5 + 0 + 0 + 2 = 7 ~ (đủ ~ M ~).
2. Với ~ H = 16 ~:
   • Cây 1: ~ 20 - 16 = 4 ~.
   • Cây 2: ~ 15 - 16 = 0 ~.
   • Cây 3: ~ 10 - 16 = 0 ~.
   • Cây 4: ~ 17 - 16 = 1 ~.
   • Tổng: ~ 4 + 0 + 0 + 1 = 5 ~ (không đủ ~ M ~).
3. Kết quả tối đa là ~ H = 15 ~.