Chia kẹo

chia-keoKhó

Có $n$ túi kẹo, túi thứ $i$ có $a_i$ viên. Cô giáo muốn chia cho $k$ bạn sao cho mỗi bạn nhận đúng $x$ viên lấy từ cùng một túi (một túi có thể chia cho nhiều bạn, kẹo thừa giữ lại).

Hãy tìm $x$ lớn nhất có thể. Nếu không thể chia cho đủ $k$ bạn (kể cả với $x = 1$ ), in ra $0$ .

Input

Dòng đầu gồm $n, k$ ( $1 \le n \le 10^5$ , $1 \le k \le 10^{12}$ ). Dòng thứ hai gồm $n$ số $a_i$ ( $1 \le a_i \le 10^9$ ).

Output

In ra $x$ lớn nhất.

Sample Input 1

3 5
10 7 3

Sample Output 1

Sample Input 2

2 100
5 6

Sample Output 2

Note

Nếu chia được với $x$ thì cũng chia được với mọi số nhỏ hơn — hãy chặt nhị phân trên đáp án.

Nộp bài

Code được lưu nháp tự động trên máy này.