An aisle seat, please

Time limit2sMemory limit1024 MB

Summary

Place n x-by-y seats and at least one aisle strip of width a in an l-by-w cabin so the number of seats sharing a side with an aisle is maximized.

Level: Medium6 of 10
Topics: Greedy, Math, Implementation, Geometry
Solved: No attempts yet

Problem

People who fly often like to ask for an aisle seat. Sitting by the aisle lets you stand up and stretch your legs without disturbing your neighbors.

The company <> is preparing to build a new airplane, the <<T-239- $n$ >>. The engineers must plan the cabin layout so that as many seats as possible are next to an aisle. We use the following simplified mathematical model of the cabin. In horizontal cross section, the cabin is a rectangle of length $l$ and width $w$ centimeters. A seat is a rectangle $x$ by $y$ centimeters and must be placed in the cabin so that its side of length $x$ is parallel to the side of the cabin of length $l$ . An aisle is a strip of width $a$ parallel to the side of the cabin of length $l$ . The aisle runs along the entire cabin.

The cabin must hold $n$ seats. Help the company's engineers work out how to arrange the cabin so that the maximum number of seats are next to an aisle. The cabin must have at least one aisle. A seat is considered to be next to an aisle if it shares at least one side with the aisle.

Input

The input file contains six integers: $n$ , $l$ , $w$ , $x$ , $y$ , and $a$ ( $1 \le n \le 10\,000$ , $1 \le l, w, x, y, a \le 10^4$ ).

Output

If it is impossible to place $n$ seats in the cabin with at least one aisle, output the single number << $-1$ >>. Otherwise, output the maximum number of seats that can be placed next to an aisle.

Hint

In the first example, one optimal arrangement of the seats is the following:

Examples2

Example 1
Input
```
400 3250 750 80 60 70
```
Expected output
```
160
```
Example 2
Input
```
450 3250 750 80 60 70
```
Expected output
```
-1
```