TX202611 城市灯光切换

题目描述

城市广场上有 N 盏灯，从左到右编号为 1 至 N。

每盏灯有两种状态：

• 0 表示关闭；
• 1 表示开启。

现在已知所有灯的初始状态和目标状态。管理员希望通过操作，使每盏灯都变成对应的目标状态。

管理员使用的控制器有一个固定参数 K。每次操作必须选择恰好连续的 K 盏灯，同时切换它们的状态：

• 原来为 0 的变成 1；
• 原来为 1 的变成 0。

不同操作选择的范围可以重叠。同一盏灯被切换两次后，会恢复到操作前的状态。

请你计算：最少需要多少次操作，才能让所有灯达到目标状态。

如果无论如何操作都无法完成，输出 -1。

输入格式

第一行包含两个正整数 N 和 K。

第二行包含一个长度为 N 的 01 字符串 S，表示初始状态。

第三行包含一个长度为 N 的 01 字符串 T，表示目标状态。

输出格式

输出一个整数，表示最少操作次数。

如果无法完成，输出 -1。

样例 1 输入

5 3
00000
11011

样例 1 输出

2

样例 1 说明

可以进行以下操作：

1. 切换第 1 至第 3 盏灯：

   00000 → 11100
   

2. 切换第 3 至第 5 盏灯：

   11100 → 11011
   

两次操作后达到目标状态，且无法只用一次操作完成。

样例 2 输入

3 2
000
111

样例 2 输出

-1

样例 2 说明

无论切换第 1 至第 2 盏灯，还是第 2 至第 3 盏灯，都不能使三盏灯同时变为开启状态；两次切换会使中间一盏灯恢复为关闭状态。因此无法达到目标状态。

数据范围

• 1 ≤ K ≤ N ≤ 10^6
• S 和 T 的长度均为 N
• S 和 T 只包含字符 0、1

子任务如下，各子任务独立计分：