Training Site
Sideways banner

Steps to Heaven

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

John and Mary are running up the steps to get to the temple high above the clouds in the mountain, chanting Left Right... in time with each other.

They both want to get to the temple ahead of the other. The temple has N steps leading up to it.

Every second, both John and Mary will make a leap, starting with their left foot. John's left foot leaps over A steps at a time, and his right foot leaps over B steps at a time. Mary's left foot leaps over C steps at a time, and her right foot leaps over D steps at a time.

Who will get to the temple first, and how much many seconds before the other?


The first line contains a single integer, N, the number of steps leading to the temple.

The second line contains four integers, A, B, C and D - the number of steps for each leap.


Print a single integer - the number of seconds difference between their arrival times. If John arrives first, print a positive integer. If Mary arrives first, print a negative integer. If both arrive at the same time, print 0.


  • 1 \leq N \leq 1,000,000,000
  • 1 \leq A, B, C, D \leq N


  • Subtask 1 (30%): Left and right leaps are identical - A = B and C = D
  • Subtask 2 (30%): N \leq 1,000
  • Subtask 3 (40%): No further constraints apply.


In the first example, John, taking 3 steps at a time, gets there in 4 leaps. Mary, taking 2 steps at a time, gets there in 6 leaps. John arrives 2 seconds before Mary.

In the second example, John leaps 1 step, then 5 steps, then 1 step (getting to the 7th step). A final leap (normally up to 5 steps) gets him to the top. Mary, leaps 3 steps, then 2 steps, then 3 steps - getting to the top on the 3rd leap. Mary arrives 1 second before John.

  • Sample Input 1

    3 3 2 2

    Sample Output 1

  • Sample Input 2

    1 5 3 2

    Sample Output 2