Donut Challenge

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. The original guarantees feasibility; on this site n≤h.

输出格式

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
2

输出：

2

样例说明

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