Author: | A. Klenin, I. Tuphanov | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
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.
The input file contains integers WHwhD. It is guaranteed that the answer exists for given input.
Output must contain a single integer — the minimum number of rolls.
1≤W,H,w,h≤109; 1≤D≤2×109;
h≤H; w≤W;
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|