Training Site
Sideways banner


Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 0.5 seconds

Alice has a large rectangular sheet of paper, measuring X units wide and Y units high. She would like to cut this into several smaller sheets to use for her origami. Each origami sheet must be of the same size: A units wide and B units high.

Alice has a fancy machine that can perform any number of simultaneous horizontal and/or vertical cuts across the paper. Each cut must be parallel to an edge of the paper, and partial cuts are disallowed – every cut must span the entire width or height of the original sheet of paper.

What is the maximum number of origami sheets that can be produced in this manner from the larger sheet? Note that the origami sheets may be cut at any orientation (sheets of either A \times B or B \times A are allowed).


There will be a single line containing four space-separated integers: X, Y, A, and B.


You should print a single integer – the maximum number of origami sheets that can be produced.


  • 1 \le X, Y, A, B \le 10\,000


  • Subtask 1 (30%): A = B = 1
  • Subtask 2 (30%): A = B
  • Subtask 3 (40%): No further restrictions apply
  • Sample Input 1

    2 3 1 1

    Sample Output 1

  • Sample Input 2

    7 8 2 2

    Sample Output 2

  • Sample Input 3

    5 3 1 2

    Sample Output 3