## Problem D. Door and wallpaper ≡

• problems
 Author: A. Klenin, I. Tuphanov Time limit: 1 sec Input file: input.txt Memory limit: 256 Mb Output file: output.txt

### Statement

Young builder Vasya was requested to hang wallpaper on the wall. The wall is a rectangle of W meters wide and H meters high, with a rectangular door of w meters wide and h meters high, located at the left side of the wall. Wallpaper is packaged into rolls. Each roll is 1 meter wide and D meters long, which Vasya may have to cut into shorter stripes of equal width.

Vasya has a high standard for work quality, so he must:

• Cover with wallpaper the entire wall except for the door, without gaps or overlapping.
• Hang wallpaper in vertical stripes of length H − h over the door and H elsewhere.
• Cut all rolls into the same sequence of stripe lengths.

Your program must calculate the minimum number of wallpaper rolls required to complete the task.

In the example below it is optimal to cut rolls into stripes of lengths 3+2+1. If different rolls could be cut into different stripe sequences, then a better solution would be to cut one roll into lengths 3+3 and another one into 2+2+2.

### Input file format

The input file contains integers W H w h D. It is guaranteed that the answer exists for given input.

### Output file format

Output must contain a single integer — the minimum number of rolls.

### Constraints

1 ≤ W, H, w, h ≤ 109; 1 ≤ D ≤ 2 × 109;

h ≤ H; w ≤ W;

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 3 1 6

3


0.070s 0.011s 13