Cheburashka loves tangerines. Now he was at the New Year's fair among a large number of boxes of tangerines. The ith box contains bi bananas. The fair starts its work in h hours.
Cheburashka is very smart and can choose the speed of eating tangerines - k mandarins per hour. He then selects a box of tangerines every hour and gobbles up k pieces from that box. If there are less than k tangerines in the box, then Cheburashka will eat them all and will not touch any more tangerines during this hour.
Cheburashka likes to eat slowly, but wants to eat all the tangerines before the fair opens.
Help Cheburashka find the minimum speed of eating tangerines, but such that he can still eat all the tangerines.
Input
The first line contains the number
n (
1 <= n <= 104) - the number of boxes with tangerines. The second line contains
n numbers
bi - the number of tangerines in the
i-th box (
1 < ;= bi <= 109). The third line contains the number
h (
n <= h <= 109) - after how many hours the fair opens.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
4
3 6 7 11
8 |
4 |
| 2 |
5
30 11 23 4 20
5 |
30 |
| 3 |
5
30 11 23 4 20
6 |
23 |