---{"category_name":"easy","problem_code":"ZEBRA","problem_name":"Zebra Crossing","problemComponents":{"constraints":"- $1 \\leq T \\leq 10^5$\n- $2 \\leq N \\leq 10^3$\n- $1 \\leq K \\leq N$\n- Sum of $N$ over all test cases does not exceed $5 \\cdot 10^5$","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"- The first line contains an integer $T$ denoting the number of test cases. The $T$ test cases then follow.\n- The first line of each test case contains two integers $N$ and $K$.\n- The second line of each test case consists of a binary string of length $N$ denoting the color of blocks of the zebra crossing.\n","inputFormatState":true,"outputFormat":"For each test case, output the farthest block Chef can reach with exactly $K$ jumps, or `-1` in case Chef cannot jump exactly $K$ times.","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"3\n6 2\n100101\n5 1\n10111\n6 1\n000000\n","output":"6\n2\n-1\n","explanation":"- For the first test case, Chef can jump in the following order: $1 \\rightarrow 5 \\rightarrow 6$.\n\n- For the second test case, Chef can jump in the following order: $1 \\rightarrow 2$.\n\n- For the third test case, Chef cannot make any jumps.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/tYdaAF0-ZRw","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":0.5,"source_sizelimit":50000,"problem_author":"ashishgup","problem_tester":"","date_added":"17-09-2021","tags":{"0":"ashishgup","1":"cook133","2":"cook133","3":"parity","4":"parity","5":"simple","6":"simple"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/ZEBRA","time":{"view_start_date":1632078002,"submit_start_date":1632078002,"visible_start_date":1632078002,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=ZEBRA","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problems statements in [Russian](https://www.codechef.com/download/translated/COOK133/russian/ZEBRA.pdf) and [Bengali](https://www.codechef.com/download/translated/COOK133/bengali/ZEBRA.pdf).There's a zebra crossing appearing in the middle of nowhere with $N$ blocks in it. The colors of the zebra crossing is represented by a binary string $S$, where $S_i$ is `1` if the $i$-th block from the left is white, and `0` if the block is black.Chef really wants to play with the zebra crossing. Although the given zebra crossing might not have alternate black and white blocks, Chef wants to follow the alternating white-black color pattern while crossing it.Initially, Chef stands at block $1$. Chef has to jump **exactly** $K$ times, and in each jump he has to move forward and jump to a different color than that previously occupied by Chef. More formally, suppose that Chef is currently at block $i$ and wants to jump to block $j$ then following conditions should hold:- $i < j$- $S_i \neq S_j$Output the farthest block Chef can reach with exactly $K$ jumps. If Chef cannot jump exactly $K$ times, output `-1`.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>