Dây cáp

Cho \(n\) đoạn dây cáp, đoạn dây thứ \(i\) có độ dài \(a_i\). Cần cắt các đoạn dây thành các đoạn nhỏ hơn sao cho có được \(k\) đoạn dây bằng nhau có độ dài nguyên. Có thể không cần cắt hết các đoạn dây đã cho. Mỗi đoạn dây bị cắt có thể có phần còn thừa khác \(0\).

Yêu cầu: Xác định độ dài lớn nhất của đoạn dây có thể nhận được. Nếu không có cách cắt thì đưa ra số \(0\).

Input

Dữ liệu vào Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương \(n, k\) (\(1 \le n \le 10^5\), \(1 \le k \le 10^{18}\)).

• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên dương \(a_i\) (\(1 \le a_i \le 10^9\)) là độ dài của dây cáp thứ \(i\).

Ràng buộc:

• \(40\%\) số test ứng với \(40\%\) số điểm có \(n = 1\).

• \(40\%\) số test ứng với \(40\%\) số điểm có \(1 \le n, a_i \le 10^3\).

• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có giới hạn gì thêm.

Output

In ra một số nguyên duy nhất là kết quả bài toán.

Example

Input:

3 5
48
29
6

Output:

14

Note

Cắt \(3\) đoạn dây có độ dài lần lượt là \(48\), \(29\), \(6\) để có \(5\) đoạn dài nhất với độ dài bằng nhau, cách cắt tối ưu là:

• Dây thứ nhất: cắt được \(3\) đoạn độ dài \(14\) (thừa \(6\)).

• Dây thứ hai: cắt được \(2\) đoạn độ dài \(14\) (thừa \(1\)).

• Dây thứ ba: không cắt được đoạn nào (phần dư là \(6\)).
  Tổng cộng có \(5\) đoạn độ dài \(14\). Với độ dài \(15\) chỉ cắt được \(3 + 1 + 0 = 4\) đoạn nên không đủ.