Skip to content
AlgoArena

Navruz Garlands

Easy 1 s 256 MBbinary searchgreedy

Navruz is coming, and Dilnoza is decorating her shop. The shop has NN ribbons, and the ii-th ribbon has an integer length of aia_i centimeters. Dilnoza wants to make garlands from pieces of the same integer length LL. A ribbon of length aia_i can be cut into ⌊ai/L⌋\lfloor a_i / L \rfloor pieces of length LL. The leftover part of each ribbon is thrown away, and ribbons cannot be glued together. Dilnoza needs at least KK pieces. Find the maximum integer L≥1L \ge 1 such that she can obtain at least KK pieces of length LL. If it is impossible even for L=1L = 1, print 00.

Input

The first line contains two integers NN and KK (1≤N≤2×1051 \le N \le 2 \times 10^5, 1≤K≤1091 \le K \le 10^9) — the number of ribbons and the required number of pieces.

The second line contains NN integers a1,a2,…,aNa_1, a_2, \dots, a_N (1≤ai≤1091 \le a_i \le 10^9) — the lengths of the ribbons.

Output

Print one integer — the maximum length LL of a piece such that at least KK pieces can be obtained, or 00 if it is impossible even for L=1L = 1.

Log in to rate this problem5.0 average · 1 ratings

Examples

Input 1
4 7
9 7 5 3
Output 1
3

Explanation

In the first example, for L=3L = 3 we get ⌊9/3⌋+⌊7/3⌋+⌊5/3⌋+⌊3/3⌋=3+2+1+1=7\lfloor 9/3 \rfloor + \lfloor 7/3 \rfloor + \lfloor 5/3 \rfloor + \lfloor 3/3 \rfloor = 3 + 2 + 1 + 1 = 7 pieces, which is enough. For L=4L = 4 we get only 2+1+1+0=42 + 1 + 1 + 0 = 4 pieces, which is not enough, and a larger LL gives even fewer. So the answer is 33.

Input 2
2 10
3 4
Output 2
0