Minimum Eating Speed

In each unit of time you can eat from only one box/pile, at most d items; eating fewer than d still uses a full unit of time, and leftover capacity cannot carry over to the next box/pile. Find the minimum positive integer speed that finishes everything within the deadline.

输入格式

The first line contains n, the second line contains n quantities, and the third line contains the deadline h. The original numeric upper bounds are missing; this site adds 1≤n≤200000, quantities in 1..10^9, and h≤10^18. On this site 1≤h; the original does not guarantee feasibility, so this site outputs −1 when it is infeasible.

输出格式

Output a single integer answer.

样例 1

输入：

4
4 9 11 17
8

输出：

6

样例 2

输入：

4
3 6 7 11
8

输出：

4

样例 3

输入：

2
2 2
1

输出：

-1

样例说明

The outputs of the three public examples are, in order: 6; 4; -1. Verified by independent enumeration or direct simulation.