Чебурашка обожает мандарины. Сейчас он оказался на новогодней ярмарке среди большого количества ящиков с мандаринами. В i-м ящике bi мандаринов. Ярмарка начинает свою работу через h часов.
Чебурашка очень умный и может выбрать скорость поедания мандаринов - k мандаринов в час. Затем он каждый час выбирает ящик мандаринов и уплетает k штук из этого ящика. Если в ящике меньше k мандаринов, то Чебурашка съест их все и больше не притронется ни к одному мандарину в течение этого часа.
Чебурашка любит есть медленно, но желает съесть все мандарины до открытия ярмарки.
Помогите найти Чебурашке минимальную скорость поедания мандаринов, но такую, чтобы он все-таки смог съесть все мандарины.
Входные данные
В первой строке записано число
n (
1 <= n <= 104) - количество ящиков с мандаринами. Вторая строка содержит
n чисел
bi - количество мандаринов в
i-м ящике (
1 <= bi <= 109). В третьей строке записано число
h (
n <= h <= 109) - через сколько часов открывается ярмарка.
Выходные данные
Выведите ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
| 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 |