Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Để chuẩn bị cho ngày lễ Noel bạn An chuẩn bị ~N~ đoạn dây trang trí (đoạn dây thứ ~i~ có độ dài ~a_i~) và ~M~ đèn. An muốn cắt ~N~ đoạn dây này thành ~M~ đoạn bằng nhau để treo đèn, mỗi dây treo 1 đèn. Yêu cầu mỗi đoạn có độ dài nguyên. Không nhất thiết cắt hết tất cả đoạn dây ban đầu và phần thừa cắt đi có thể có độ dài khác 0.

Yêu cầu: Hãy giúp An tìm độ dài lớn nhất mà đoạn dây có thể nhận được. Nếu không thể cắt thì đưa ra số 0.

Dữ liệu vào

• Dòng đầu chứa 2 số nguyên ~N~, ~M~.
• Dòng thứ ~i~ trong ~N~ dòng sau chứa số nguyên ~a_i~.

Kết quả

• Ghi kết quả trên 1 dòng dưới dạng số nguyên.

Giới hạn

• ~1 \le N \le 10^5~, ~1 \le a_i \le 10^9~, ~1 \le M \le 10^{18}~.
• (Đề gốc không ghi giới hạn; trên hệ thống dùng giới hạn trên.)

Sample Input 1

4 11
802
743
547
539

Sample Output 1

200

Giải thích

Chọn độ dài 200: các sợi ~802, 743, 547, 539~ cắt được lần lượt ~4, 3, 2, 2~ đoạn, tổng ~11 \ge 11~. Còn độ dài 201 chỉ cắt được ~3 + 3 + 2 + 2 = 10 < 11~ đoạn. Mỗi đoạn phải nằm trọn trong một sợi dây, không được nối các mẩu thừa lại với nhau.