Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: kelione_namo_2.in

Rezultatų failas: kelione_namo_2.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kelionė namo 2

Ant Ox ašies gyvena varlė ir jai reikia parsigauti namo. Varlės namai yra taške n, o varlė šiuo metu yra taške 1. Vienu ėjimu varlė gali šokti į dešinę per atstumą, nedidesnį už d. Taigi, jei einamuoju momentu varlė yra taške x, tai po vieno šuolio ji gali atsidurit taške x+a, kur a yra sveikasis skaičius tarp 1 ir d imtinai.

Kiekvienam taškui tarp 1 ir n yra žinoma, ar tame taške yra lelijos lapas. Žinoma, varlė gali šuoliuoti tik ant lelijų lapų (nes sušlapti juk niekas nenori, net ir varlės). Yra garantuota, kad taškuose 1 ir n visada bus lelijos.

Jums reikia nustatyti mažiausią reikiamą šuolių skaičių, kad varlė galėtų grįžti namučių. Jei namo grįžti nepavyks, varlę ištiks liūdesiukas ir tokiu atveju turite atspausdinti -1.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai n ir d (2\\leqn\\leq10^6,1\\leqd\\leqn-1).

Antroje eilutėje pateikta simbolių seka s, kurią sudaro n simbolių. Kiekvienas iš šių simbolių yra arba 0, arba 1. Jei i-asis simbolis yra 0, tai taške i lelijos nėra, o kitu atveju yra. Galite tarti, kad pirmas ir paskutinis simboliai šioje simbolių sekoje visada bus lygūs 1.

Rezultatai

Jūsų programa turi išvesti vieną sveikąjį skaičių - mažiausią reikiamą šuoliukų skaičių. Jei taško n pasiekti pradedant taške 1 neįmanoma, spausdinkite -1.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
8 4
10010101
 
2
 
4 2
1001
 
-1
 
8 4
11100101
 
3
 
12 3
101111100101
 
4

Paaiškinimas

Pirmajame pavyzdyje varlė namus gali pasiekti dviem šuoliais: pirmuoju šuoliu varlė šoka iš taško 1 į tašką 4 (šuolio ilgis yra 3), o antruoju šuoliu - iš taško 4 į tašką 8 (šuolio ilgis 4).

Antrajame pavyzdyje varlė niekaip negali grįžti namo, nes atstumas, kurį reikia nušokti, yra 3, tačiau varlė negali nušokti toliau daugiau 2.