Elevator

Interview

Time limit1sMemory limit256 MB

Summary

An elevator with buttons that move up U or down D floors, staying within floors 1 to F, needs the minimum presses to go from floor S to floor G.

Level: Medium4 of 10
Topics: BFS, Graph, Shortest path, Implementation
Solved: No attempts yet

Problem

Kangho applied to a coding-education startup, and today is his interview day. But he overslept and arrived late at the building where the company is located.

The company occupies a tall building with $F$ floors in total, and its office is on floor $G$ . Kangho is currently on floor $S$ and wants to take the elevator to floor $G$ .

A normal elevator has a button for every floor, but the elevator Kangho boarded has only two buttons.

Button U: go up by $U$ floors.
Button D: go down by $D$ floors.

If going up by $U$ floors would rise above the top floor ( $F$ ), or going down by $D$ floors would drop below floor $1$ , the elevator does not move.

Find the minimum number of button presses Kangho needs to reach floor $G$ . If he cannot reach floor $G$ using only the elevator, print use the stairs.

Input

The first line contains five integers $F$ , $S$ , $G$ , $U$ , and $D$ , separated by spaces. ( $1 \le S, G \le F \le 10^6$ , $0 \le U, D \le 10^6$ )

The building starts at floor $1$ , and the highest floor is $F$ .

Output

Print the minimum number of button presses needed to go from floor $S$ to floor $G$ . If the elevator cannot reach floor $G$ , print use the stairs.

Examples2

Example 1
Input
```
10 1 10 2 1
```
Expected output
```
6
```
Example 2
Input
```
100 2 1 1 0
```
Expected output
```
use the stairs
```