Mô tả bài toán

Nhà bạn An có ~ N ~ miếng gỗ với chiều dài khác nhau. An muốn xây dựng một hàng rào gồm ~ K ~ miếng gỗ sao cho tất cả các miếng đều có chiều dài bằng nhau và chiều dài lớn nhất có thể sau khi cắt.

An có thể:

• Cắt các miếng gỗ thành các đoạn có chiều dài nguyên.
• Không ghép các đoạn từ nhiều miếng gỗ lại với nhau.

Yêu cầu: Tìm chiều dài lớn nhất của một miếng gỗ có thể đạt được để tạo thành hàng rào gồm ~ K ~ miếng.

Input:

1. Dòng đầu chứa hai số nguyên ~ N ~ và ~ K ~ (~ 1 \leq N \leq 10^5 ~, ~ 1 \leq K \leq 10^9 ~).
2. Dòng thứ hai chứa ~ N ~ số nguyên ~ l_1, l_2, \ldots, l_N ~ (~ 1 \leq l_i \leq 10^9 ~): chiều dài của từng miếng gỗ.

Output:

• In ra chiều dài lớn nhất có thể đạt được. Nếu không thể cắt đủ ~ K ~ miếng, in ra ~ 0 ~.

Input:

3 4
15 10 8

Output:

7

Giải thích:

1. Với ~ x = 7 ~:
   • ~ \lfloor 15 / 7 \rfloor = 2 ~, ~ \lfloor 10 / 7 \rfloor = 1 ~, ~ \lfloor 8 / 7 \rfloor = 1 ~.
   • Tổng ~ 2 + 1 + 1 = 4 ~, đủ ~ K ~ đoạn.
2. Với ~ x = 8 ~:
   • ~ \lfloor 15 / 8 \rfloor = 1 ~, ~ \lfloor 10 / 8 \rfloor = 1 ~, ~ \lfloor 8 / 8 \rfloor = 1 ~.
   • Tổng ~ 1 + 1 + 1 = 3 ~, không đủ ~ K ~ đoạn.
3. Kết quả tối đa là ~ x = 7 ~.