H. Parallel Checking
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The competition has ended — and now Artem only needs to check the submissions of the teams for plagiarism.

Artem has a total of $$$n$$$ submissions, and checking the $$$i$$$-th submission will take $$$A_i$$$ quanta of time.

The problem is that the checking cannot take too long — it must be completed in no more than $$$T$$$ quanta of time.

To speed up the process, Artem can parallelize it by allocating $$$d$$$ threads. In this case, the $$$i$$$-th submission will be checked in $$$\lceil\frac{A_i}{d}\rceil$$$ quanta of time (the result of integer division, rounded up).

Help Artem find the minimum number of threads $$$d$$$ such that $$$\sum{\lceil\frac{A_i}{d}\rceil} \le T$$$.

Input

The first line contains two integers $$$n$$$ and $$$T$$$ $$$(1 \le n \le 2 \cdot 10^5; n \le T \le 10^{12})$$$ — the number of available submissions.

The second line contains $$$n$$$ integers $$$A_i$$$ $$$(1 \le A_i \le 10^{12})$$$ — the number of quanta of time required to check the $$$i$$$-th submission.

Output

In a single line, output an integer $$$d$$$ $$$(1 \le d \le 10^{12})$$$ — the minimum number of threads such that $$$\sum{\lceil\frac{A_i}{d}\rceil} \le T$$$.

Example
Input
5 22
15 130 120 78 43
Output
20
Note

First test example

For $$$d = 20$$$, the submissions are checked in:

  • $$$\lceil\frac{15}{20}\rceil = 1$$$;
  • $$$\lceil\frac{130}{20}\rceil = 7$$$;
  • $$$\lceil\frac{120}{20}\rceil = 6$$$;
  • $$$\lceil\frac{78}{20}\rceil = 4$$$;
  • $$$\lceil\frac{43}{20}\rceil = 3$$$.

In total, for $$$d = 20$$$, $$$1 + 7 + 6 + 4 + 3 = 21$$$ quanta of time are used.

For $$$d = 19$$$, the submissions are checked in:

  • $$$\lceil\frac{15}{19}\rceil = 1$$$;
  • $$$\lceil\frac{130}{19}\rceil = 7$$$;
  • $$$\lceil\frac{120}{19}\rceil = 7$$$;
  • $$$\lceil\frac{78}{19}\rceil = 5$$$;
  • $$$\lceil\frac{43}{19}\rceil = 3$$$.

In total, for $$$d = 19$$$, $$$1 + 7 + 7 + 5 + 3 = 23$$$ quanta of time are used.

Similarly, it can be shown that for all $$$1 \le d \lt 19$$$, the number of quanta of time is also at least $$$23$$$.

Thus, it follows that for $$$T = 22$$$, the value $$$d = 20$$$ is the minimum possible.