Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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?

Input

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.

Output

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.

Constraints

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

Subtasks

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

Explanation

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

    12
    3 3 2 2
    

    Sample Output 1

    2
    
  • Sample Input 2

    8
    1 5 3 2
    

    Sample Output 2

    -1