Có ~n~ sợi dây thép, sợi thứ ~i~ có độ dài ~a_i~. Người ta cần cắt các sợi đã cho thành các đoạn sao cho có được ~K~ đoạn thép bằng nhau có độ dài là số nguyên. Có thể không cần cắt hết các sợi đã cho, mỗi sợi bị cắt có thể có phần còn thừa khác 0.

Yêu cầu: Tìm độ dài lớn nhất của ~K~ đoạn thép có thể nhận được.

Dữ liệu vào

Đọc từ tệp văn bản CATTHEP.INP gồm:

• Dòng đầu tiên ghi hai số nguyên ~n, K~;
• Dòng thứ hai ghi ~n~ số nguyên ~a_i~;
• Các số trên một dòng cách nhau ít nhất một dấu cách.

Kết quả

Ghi vào tệp văn bản CATTHEP.OUT một số duy nhất là kết quả tìm được.

Ví dụ

Input:

4 8
16 34 68 43

Output:

17

Giới hạn

• ~1 \le n \le 5 \times 10^5~
• ~0 < K \le 10^9~
• ~0 < a_i \le 10^9~
• Có ~60\%~ số điểm tương ứng với ~1 \le n \le 3 \times 10^3~.
• Có ~40\%~ số điểm tương ứng với ~3 \times 10^3 < n \le 5 \times 10^5~.