All submissions for this problem are available.Madam EEE decided to take a surprise CT in her class. Of course, she doesn’t like partial scoring. So, she assigned each student a grade of $0$ or $1$. Of course, a lot of students got a zero in the exam. So they are sad. No worries. It’s hackerman Zawad to the rescue. Being the legendary hacker he is, Zawad can hack into the PC of madam EEE and change the results of the CT. Being a member of the BUET Chirokumar Songho, Zawad cannot stand girls. So, he wishes to change each girls grade to $0$ and each boy’s grade to $1$. The results of the CT are represented as an string of $0$’s and $1$’s. The $i$th of the represents the grade of student no $i$. In a single operation, Zawad can flip (change $1$ to $0$ and $0$ to $1$) any $k$ consecutive values. He wants to perform as few as operations as possible for not raising madam EEE’s suspicions. Help Zawad figure out the minimum number of operation to achieve his goals. ###Input: The first line contains a single integer $t$, the number of testcases. Each testcase consists of three lines. The first line contains two integers $n$, the number of students and $k$. The second line contains a string of $n$ characters. The $i$th character represents the grade of the $i$th student. Each character is either $0$ or $1$. The third line contains a string of $n$ characters. The $i$th character is $1$ if the $i$th student is a boy, $0$ if she is a girl. ###Output: For each case output a single line containing a single integer, the minimum number of operations to change each girls grade to $0$ and each boys grade to $1$. If it is not possible, output $-1$. ###Constraints - $1 \leq t \leq 10$ - $1 \leq k \leq n \leq 10^5$. ###Sample Input: 4 3 2 101 011 5 3 00111 11100 4 4 0110 1110 5 4 01110 01110 ###Sample Output: 1 2 -1 0 ###EXPLANATION: In the first sample, Zawad can achieve his objective in a single operation by flipping the first two values. So, the answer is $1$. In the second sample, Zawad can first flip indices $3$ to $5$. Then the string becomes $00000$. Next he flips indices $1$ to $3$. Then the string becomes $11100$. So, the answer is $2$. In the third sample, there is no way to achieve Zawad’s goals. In the fourth sample, each girl already has $0$ grade and each boy $1$. So, we don’t need to perform any operations.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.