Bits Transformation

Cerință

Aflat pentru prima dată la olimpiada de informatică, Gigel își dorește să impresioneze pe toată lumea. Pentru a face aceasta, el desenează pe tablă un șir $A$, conținând $N$ valori ce pot fi $0$ sau $1$, urmând ca după probă, el să facă un truc magic cu acesta (ceva legat de maști pe biți, s-a gandit el). Din păcate, în timpul probei, unul din prietenii lui cei mai buni, vrând să îi joace o farsă, a modificat șirul $A$ folosind următorul tip de operație de un număr arbitrar de ori:

1. A ales o subsecvență de dimensiune $K$ din șirul $A$.
2. A dat flip tuturor valorilor din subsecvența aleasă.

Olimpiada este pe sfarșite, iar Gigel își dorește să își ducă la bun sfarșit trucul magic, așadar vă roagă pe voi să gasiți numărul minim de operații care trebuie aplicate noului șir pentru a îl aduce înapoi la șirul inițial, sau să îi spuneți în cazul in care acest lucru este imposibil.

Date de intrare

Pe prima linie a fișierului de intrare bitstransform.in se găsesc două numere întregi, $N$ și $K$.
A doua linie va conține $N$ valori de $0$ sau $1$, reprezentând șirul $A$.
A treia linie va conține $N$ valori de $0$ sau $1$, reprezentând șirul $B$.

Date de ieșire

Pe prima linie a fișierului de ieșire bitstransform.out se va găsi un singur număr întreg, numărul minim de operații pentru a-l transforma pe $B$ in $A$, sau -1 în cazul în care nu există soluție.

Restricții și precizări

• $1 \leq K \leq N \leq 1 \ 000 \ 000$;
• Pentru teste in valoare de 20 de puncte se garanteaza că $1 \leq N \leq 100$.
• Pentru teste in valoare de 20 de puncte se garanteaza că $1 \leq N \leq 1 \ 000$.
• Pentru teste in valoare de 20 de puncte se garanteaza că $1 \leq N * K \leq 1 \ 000 \ 000$.
• Pentru teste in valoare de 30 de puncte nu exista alte restricții.
• Se vor oferi 10 puncte din oficiu.

Exemplul 1

bitstransform.in

5 2
1 0 1 1 1
0 0 0 0 0

bitstransform.out

3

Explicație

Subsecvențele cărora le vom da flip sunt [4, 5], [1, 2], [2, 3], pentru un total de 3 operații.

Exemplul 2

bitstransform.in

5 2
1 0 1 1 0
0 0 0 0 0

bitstransform.out

-1

Explicație

Șirul inițial nu poate fi obțtinut folosind doar operațiile precizate in enunț.