Minimum Soldering Speed

Hard#searching #binary-search #binary-search-on-answer· solved by 0 · time limit 2.0 s

There are $n$ boards; board $i$ has $a_i$ joints to solder. You solder at a fixed speed of $k$ joints per hour, working on one board per hour (if a board has fewer than $k$ joints left, you finish it and rest for the rest of that hour). What is the smallest integer $k$ that finishes everything within $h$ hours?

Try binary search on the answer.

Input

$n$ , then $a_1 \dots a_n$ , then $h$ .

Output

The minimum speed $k$ .

Constraints

$1 \le n \le 10^4$ , $n \le h \le 10^9$ , $1 \le a_i \le 10^9$

Sample 1

Input

4
3 6 7 11
8

Output

Sample 2

Input

5
30 11 23 4 20
5

Output