Мостостроение

면접 대비

시간 제한2초메모리 제한512 MB

요약

길이 a인 통나무 x개와 길이 b인 통나무 y개로 l개의 줄을 만들 때, 각 줄은 통나무 하나 이상으로 구성되며 줄 너비의 최솟값을 최대로 하는 값을 구한다.

난이도: 보통10점 중 5점
유형: 이분 탐색, 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

В деревне Гадюкино регулярно идут проливные дожди, в результате чего речка Вонючка, которую обычно можно просто перешагнуть, выходит из берегов. Чтобы можно было перейти разлившуюся реку, планируется построить плавучий мост из бревен, оставшихся от строительства бани бизнесмена, поселившегося неподалеку.

Все оставшиеся бревна имеют одинаковую толщину. При этом есть $x$ бревен длины $a$ и $y$ бревен длины $b$ . Построенный мост должен состоять из $l$ рядов, каждый из которых составлен из одного или нескольких бревен. Пилить бревна нельзя, так как последняя пила утонула при разливе Вонючки.

Главный инженер хочет построить мост максимальной возможной ширины, при этом ширина моста определяется по минимальной ширине ряда бревен.

Например, если нужно построить мост из семи рядов, и при этом есть шесть бревен длины 3 и десять бревен длины 2, то можно построить мост ширины 5.

입력

Входной файл содержит пять натуральных чисел: $x$ , $a$ , $y$ , $b$ и $l$ . Все числа не превышают 150. Общее количество бревен не меньше $l$ .

출력

Выведите в выходной файл одно число --- максимальную возможную ширину моста.

예제2

예제 1
입력
```
6 3 10 2 7
```
예상 출력
```
5
```
예제 2
입력
```
10 7 20 9 25
```
예상 출력
```
9
```