题目描述

汇总的题面 pdf 放到了本题的附加文件中。

给定正整数 $n$ 和两个长度为 $n$ 的 $\tt 01$ 串 $S$ 和 $T$。每次你可以选择一个长度为 $k$ 的区间 $[p,p+k-1]$，将 $S[p \cdots p+k-1]$（也就是 $S[p],S[p+1],\cdots,S[p+k-1]$）$\tt 01$ 翻转（$\tt 0$ 变成 $\tt 1$，$\tt 1$ 变成 $\tt 0$）。

请你求出，最少用多少次操作可以把 $S$ 变为 $T$，或者指出不可能做到（此时输出 -1）。

输入格式

第一行两个整数 $n,k$，分别表示两个 $\tt 01$ 串的长度与每次操作的区间长度。

第二行、第三行各有一个长度为 $n$ 的 $\tt 01$ 串，表示 $S$ 和 $T$。

输出格式

一行一个整数，表示答案。

输入样例 #1

6 3
000000
110110

输出样例 #1

2

输入样例 #2

8 3
00000000
10010010

输出样例 #2

-1

说明提示

对于所有的数据，$1 \le n \le 10^6$。

本站补充：原套别：第 13 套 A 题。