Thang Máy


Submit solution

Points: 2
Time limit: 1.0s
JAVA11 2.0s
Pypy 3 2.0s
Memory limit: 1000M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Một tòa nhà cao \(n\) tầng được đánh số từ tầng \(1\) đến tầng \(n\) có lắp thang máy. Hiện nay thang máy bị trục trặc do đó mỗi lần có thể di chuyển lên đúng \(k\) tầng hoặc di chuyển xuống đúng \(m\) tầng nếu có đủ không gian để di chuyển. Thang máy đang ở tầng \(s\) một người ở đó muốn di chuyển đến tầng \(f\) hỏi số bước di chuyển ít nhất để đến được tầng \(f\), nếu không di chuyển được hãy xuất ra \(-1\).

Input

Dòng đầu chứa \(n\) là số tầng của tòa nhà \((1 < n < 300)\).

Dòng thứ hai chứa hai số \(k\) và \(m\) tương ứng là số tầng lên và xuống mỗi lần di chuyển của thang máy \((1 \le k, m \le 50)\).

Dòng thứ ba chứa \(s\) và \(f\) \((1 \le s, f \le n)\) là vị trí tầng xuất phát và đích đến.

Output

Số bước ít nhất di chuyển thang máy, nếu không đến được đích bạn hãy xuất ra \(-1\).

Example 1

Input

12
5 7
1 8

Output

11

Giải thích: xuất phát từ tầng \(1\) mỗi lần lên đúng \(5\) tầng hoặc xuống đúng \(7\) tầng nếu có đủ không gian để lên hoặc xuống do đó cần \(11\) bước chuyển thang qua các tầng \(1\to6\to11\to4\to9\to2\to7\to12\to5\to10\to3\to8\).

Example 2

Input

120
15 57
18 112

Output

-1
tichpx

Comments


  • 0
    hung_181503676  commented on Oct. 23, 2019, 4:51 a.m.

    bài này việc lên xuống khi mà ko có giới hạn dừng thì làm sao xuất ra -1 đc ạ?


    • 3
      TICHPX  commented on Oct. 23, 2019, 6:58 a.m.

      Xuất ra \(-1\) khi không có cách nào dừng ở đúng tầng f