Koko Eating Bananas

Problem statement

An animal-care center has several piles of bananas to distribute before its evening deadline. Its feeder works at a fixed integer rate, but during one hour it can work on only one pile; unused time after finishing that pile cannot be transferred to another. Your task Find the smallest positive integer rate k that allows all piles to be consumed within h hours. In each hour, consume min(k, remaining bananas) from one chosen pile. Important details A partly consumed pile can be resumed later. Each nonempty pile needs at least one hour, and h is at least the number of piles. Use a monotonic feasibility check and binary search rather than trying every possible rate. Worked example For piles [4, 8] and h = 3, rate 4 takes one hour plus two hours. Rate 3 takes two plus three hours, so the minimum rate is 4.

Input format

First line: n h. Next line: n pile sizes.

Output format

Print the minimum integer rate.

Constraints

1 <= n <= 10000; n <= h <= 1000000000; 1 <= pile sizes <= 1000000000.

Sample input

2 3
4 8

Sample output

4