Stansiya
Tayvanda bütün stansiyaları birləşdirən bir dəmir yolu sistemi mövcuddur. Stansiyalar 0-dan n - 1-ə qədər nömrələnib. Hər bir qonşu stansiya arasındakı məsafə 1 kilometrdir və bəzi stansiyalarda gecələmək mümkündür. İlk və son stansiyada gecələmək mümkündür.
Can-Ci Tayvan boyunca mövcud dəmir yolu sistemi ilə səyahət etmək istəyir. O, səyahətinə başlanğıc stansiyadan başlayacaq və son stansiyada bitirəcək. Can-Ci endirimli bileti olduğuna görə bir gündə ən çox k kilometr gedə bilər. O, yalnız gecələmək mümkün olan stansiyalarda dayanmaq istəyir. Can-Cinin başlanğıc stansiyadan son stansiyaya ən az neçə günə gedə biləcəyini müəyyən edin.
Stansiyalarda gecələmək mümkün olan yerlər və k məhdudiyyəti haqqında məlumat verilir. Can-Cinin başlanğıc stansiyadan son stansiyaya gedə biləcəyini müəyyən edin. Əgər cavab müsbətdirsə, bunu edə biləcəyi ən az gün sayını göstərin.
Giriş məlumatları
Birinci sətir iki ədəd n (2 ≤ n ≤ 5 * 10^5) və k (1 ≤ k ≤ 3000) ehtiva edir. İkinci sətir lodge massivini ehtiva edir ki, bu da stansiyada gecələməyin mümkün olub-olmadığını göstərir. Əgər stansiyada gecələmək mümkündürsə, lodge[i] 1-ə bərabərdir, əks halda 0. Həm lodge[0], həm də lodge[n-1] dəyərləri 1-dir.
Çıxış məlumatları
Can-Cinin başlanğıc stansiyadan son stansiyaya gedə biləcəyi ən az gün sayını göstərin. Əgər belə bir səyahət mümkün deyilsə, -1 çıxarın.
Nümunə
Üçüncü testi nəzərdən keçirək. 10 stansiya var və 0, 1, 2, 3, 4, 6, 7, 9 stansiyalarında gecələmək mümkündür. k dəyəri 4-ə bərabərdir, yəni Can-Ci bir gündə ən çox 4 kilometr səyahət edə bilər. O zaman o, 0 stansiyasından 9 stansiyasına ən az 3 günə gedə bilər. Məsələn, o, birinci gün 0 stansiyasından 3 stansiyasına, ikinci gün 3-dən 7-yə, üçüncü gün isə 7-dən 9-a gedə bilər. Əgər k 1-ə bərabərdirsə, başlanğıc stansiyadan son stansiyaya səyahət etmək mümkün deyil.