Cu toţii cunoaştem proba “3000 de metri obstacole” de la concursurile de atletism. Sportivii pe lângă faptul că trebuie să alerge trebuie să şi sară obstacolele ce le întâlnesc. Vom codifica pista pe care se desfăşoară întrecerea prin 0 şi 1 astfel: 0 este zonă pe care sportivul poate călca, iar 1 zonă pe care trebuie obligatoriu să o sară. Astfel, pista este dată printr-o succesiune de astfel de zone, toate de aceeaşi lungime, 1cm. Sportivul ia startul imediat înaintea primei zone, iar sosirea este imediat după ultima zonă.
Pentru a parcurge pista, sportivul poate efectua o succesiune de paşi şi salturi.
La un pas el pune pe pământ un pantof, neapărat pe o zonă continuă de lungimea pantofului, formată numai din 0; pantoful poate fi plasat după pantoful de la pasul precedent, zonele ocupate de cei doi pantofi fiind parţial suprapuse sau lipite (una în continuarea celeilalte).
La un salt el pune pe pământ un pantof, neapărat pe o zonă continuă de lungimea pantofului, formată numai din 0; distanţa dintre vârful pantofului de la mişcarea precedentă şi baza pantofului de la saltul curent fiind cel mult D cm.
Se mai ştie că el poate încălţa un pantof de alergare de o dimensiune pe care şi-o poate alege (poate fi chiar şi de 1 cm!). Sportivul ştie că şansele sale de câştig sunt direct proporţionale cu lungimea pantofului pe care-l încalţă.
Cerinţă
Ajutaţi sportivul să aleagă un pantof de dimensiune cât mai mare care să-i permită terminarea cursei.
Date de intrare
Fişierul obstacole.in conţine pe prima linie numerele N şi D separate printr-un spaţiu reprezentând lungimea pistei (în cm), respectiv numărul maxim de zone pe care sportivul le poate sări. Pe linia a doua sunt N valori din mulţimea {0,1}, separate prin câte un spaţiu, reprezentând codificarea pistei, în ordine, de la start la final.
Date de ieşire
Pe prima linie a fişierului obstacole.out se află un singur număr natural ce reprezintă dimensiunea maximă a unui pantof cu care sportivul parcurge pista de la start la final. Dacă sportivul nu poate parcurge pista, se va scrie valoarea 0.
Restricţii
• 1 ≤ D < N ≤ 200000
• Ambele dimensiuni sunt numere întregi specificate în centimetri.
• Sportivul trebuie să îşi pună doi pantofi de aceeaşi lungime, unul în piciorul stâng şi unul în piciorul drept :) , şi poate să îşi suprapună parţial doi paşi consecutivi dacă el consideră aşa mai potrivit.
• Se garantează că în toate testele prima şi ultima zonă de pe pistă sunt marcate cu 1.
• Sportivul poate sări şi zone marcate cu 0.
Exemple
obstacole.in
obstacole.out
Explicaţii
14 2
1 0 0 0 1 1 0 0 1 1 0 0 0 1
2
În exemplu, cu un pantof de lungime 2, sportivul poate sari prima dată la poziţia 2 (pantoful său va ocupa poziţiile 2 şi 3). La pasul următor se deplasează o poziţie (pantoful va ocupa poziţiile 3 şi 4, de fapt avea posibilitatea să sară direct de la primul pas aici). Mai departe, sare 2 poziţii şi pantoful va ocupa poziţiile 7 şi 8 (în exemplu, poziţiile sărite au fost ambele marcate cu valoarea 1, dar el poate alege să sară şi peste unele poziţii marcate cu valoarea 0 dacă respectă regulile. La pasul următor pantoful sportivului va ocupa poziţiile 11 şi 12, apoi 12 şi 13, şi apoi reuşeşte să ajungă la final sărind ultima zonă (ar fi putut sări afară şi în momentul în care era poziţionat pe zonele 11 şi 12).