Loading [MathJax]/jax/output/CommonHTML/jax.js

Problem D. Door and wallpaper

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:

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 WHwhD. 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

1W,H,w,h109; 1D2×109;

hH; wW;

Sample tests

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

0.049s 0.007s 13