Problem Description

In the corner, an old automatic sorting machine is making a dull roaring sound.

Xiao Lan is standing by the assembly line, ready to feed a batch of wood into the machine. The distance between the machine’s baffles, $L$, is the only adjustable parameter. Any wood piece longer than $L$ will cause the conveyor belt to jam. Clearly, the smaller the baffle distance is, the higher the transport density per unit time will be. Therefore, Xiao Lan wants to set the baffle distance $L$ as small as possible.

There are $N$ original logs. The length of the $i$-th log is $A_i$. Xiao Lan can cut these logs to meet the length requirement, but due to saw blade wear, he can make at most $K$ cuts in total. The cutting rules are as follows:

1. Each cut can split one log into two pieces.
2. After splitting, the two new pieces must have positive integer lengths, and their sum must equal the length of the original log.

Now, please find the minimum feasible baffle distance $L$ for Xiao Lan, such that with no more than $K$ total cuts, after cutting, the maximum length among all wood pieces does not exceed $L$.

Input Format

The first line contains two integers $N$ and $K$, representing the number of original logs and the maximum number of cuts.

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$, representing the length of each original log.

Output Format

Output one integer, representing the minimum feasible baffle distance $L$.

1 1
5

3

2 3
9 6

3

Hint

Constraints

For $10\%$ of the testdata, $1 \le N \le 100$, $0 \le K \le 3$, $1 \le A_i \le 10^3$.

For $50\%$ of the testdata, $1 \le N \le 10^3$, $0 \le K \le 10^5$, $1 \le A_i \le 10^5$.

For $100\%$ of the testdata, $1 \le N \le 10^6$, $0 \le K \le 10^9$, $1 \le A_i \le 10^9$.

Translated by ChatGPT 5