Lại là Thang Máy


Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 1000M

Author:
Problem type

Một tòa nhà cao n tầng được đánh số từ tầng 1 đến tầng n có lắp 1 thang máy. Hiện nay thang máy bị trục trặc do đó mỗi lần có thể di chuyển k khả năng \(a_1,a_2...a_k\) tầng với \(a_i >0 \) là đi lên và \(a_i < 0\) là đi xuống nếu nó đủ không gian di chuyển tức là xuống không quá tầng 1 và lên không quá tầng 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, trường hợp không di chuyển được xuất ra -1.

Input

Dòng đầu chứa n là số tầng của tòa nhà \((1 \le n \le 10^4)\) và số nguyên dương k là số các khả năng di chuyển \(1 \le k \le 100\)

Dòng thứ 2 chứa k số nguyên có giá trị tuyệt đối không vượt quá \(10^3\) nếu âm thì thang máy đi xuống, nếu dương là thang máy đi lên

Dòng thứ 3 chứa s và f (1<=s,f<=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 xuất ra -1

Example 1

Input

12 2
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->6->11->4->9->2->7->12->5->10->3->8

Example 2

Input

120 2
-42 18
18 113

Output

-1
tichpx

Comments


  • 2
    CThành_CNTT6_K61  commented on May 29, 2021, 5:18 a.m. edited

    Em thấy vd 2 +19 14 lần và -43 4 lần có vẻ hợp lý mà thầy ơi


    • 2
      TICHPX  commented on May 29, 2021, 6:20 a.m. edited

      Cảm ơn em thầy đổi ví dụ rồi