AT_awc0005_d 配達ルートの分割

Takahashi is in charge of delivery planning at a shipping company. Today, he needs to create a plan to deliver $ N $ packages using $ K $ trucks. Each package is numbered from $ 1 $ to $ N $ , and the weight of package $ i $ is $ A_i $ . To improve delivery efficiency, he decided to arrange the packages $ 1, 2, \ldots, N $ in this order and divide them into $ K $ contiguous segments, each containing at least $ 1 $ package, and assign the packages in each segment to one truck. Every package belongs to exactly one segment, and there is a one-to-one correspondence between the $ K $ segments and the $ K $ trucks. For each truck, the sum of the weights of the packages assigned to that truck is called the **load** of that truck. Takahashi wants to maximize the smallest load among the $ K $ trucks. Considering all possible ways to divide the packages, find the maximum possible value of "the minimum load among the $ K $ trucks."

> $ N $ $ K $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ - The first line contains an integer $ N $ representing the number of packages and an integer $ K $ representing the number of trucks, separated by a space. - The second line contains $ N $ integers $ A_1, A_2, \ldots, A_N $ representing the weight of each package, separated by spaces.

Print in one line the maximum possible value of the minimum load among the $ K $ trucks when the packages are divided optimally.

### Constraints - $ 1 \leq K \leq N \leq 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - All inputs are integers.