Bridge Building

Time limit2sMemory limit512 MB

Summary

Given x logs of length a and y logs of length b, find the largest width W so that l rows of whole logs can each have total length at least W.

Level: Medium4 of 10
Topics: Implementation, Brute force
Solved: No attempts yet

Problem

Heavy rain regularly floods the Vonyuchka river in the village of Gadyukino, a stream that is normally easy to step over. To cross the flooded river, a floating bridge will be built from logs left over after a local businessman built his bath house.

All remaining logs have the same thickness. There are $x$ logs of length $a$ and $y$ logs of length $b$ . The bridge must consist of $l$ rows, and each row is made of one or more logs. Logs cannot be cut, because the last saw sank during the flood.

The chief engineer wants to build the widest possible bridge. The width of the bridge is the minimum width among its rows.

For example, if a bridge with seven rows is needed, and there are six logs of length 3 and ten logs of length 2, then a bridge of width 5 can be built.

Input

The input contains five natural numbers: $x$ , $a$ , $y$ , $b$ , and $l$ . All numbers do not exceed 150. The total number of logs is at least $l$ .

Output

Print one number: the maximum possible width of the bridge.

Examples2

Example 1
Input
```
6 3 10 2 7
```
Expected output
```
5
```
Example 2
Input
```
10 7 20 9 25
```
Expected output
```
9
```