题目背景

注意：本场比赛提交时不开启文件输入输出，与正常的梦熊周赛保持一致。

题目描述

youyou 有一个大小为 $2 \times n$ 的网格，每个格子可能是黑色或者白色。

现在 youyou 和 yy 要在这个网格上玩一个游戏：

• youyou 先选取出一个可以为空的连通块。
• 之后 yy 可以选择最多 $m$ 列，将这些列上下行的格子颜色互换。

定义一个格子集合 $S$ 为一个连通块，当且仅当 $S$ 中任意两个格子可以通过集合 $S$ 内边相邻的若干个格子连通（即四连通）。

youyou 希望最大化最终连通块中黑色格子减白色格子的数量，而 yy 希望最小化之。

现在 youyou 希望你求出：在双方都采用最优策略的情况下，最终黑色格子减白色格子的数量是多少？

输入格式

本题有多组测试数据。

第一行为两个整数 $c,T$，分别表示测试点编号和数据组数，$c = 0$ 表示该测试点为样例。

对于每一组测试数据，第一行为两个整数 $n,m$，表示给定网格图的列数和交换次数。

接下来两行，每行用一个长度为 $n$ 的 $01$ 串表示每个对应位置网格的颜色，其中 $1$ 表示黑色格子，$0$ 表示白色格子。

输出格式

对于每一组测试数据，输出一行一个数，表示最终黑色格子减白色格子的数量。

样例

0 2
5 2
11110
01001
7 1
1110000
0001111

2
4

样例 1 解释

下文中记 $(x,y)$ 表示第 $x$ 行第 $y$ 列的格子。

对于第一组数据，youyou 选择 $(1,2)$ 和 $(2,2)$ 两个格子，无论 yy 怎么交换，最终黑色格子和白色格子数量的差至少为 $2$。可以证明没有更优的解。

对于第二组数据，youyou 选择 $(1,1),(1,2),(1,3),(1,4),(2,4),(2,5),(2,6),(2,7)$ 八个格子，无论 yy 怎么交换，最终黑色格子和白色格子数量的差至少为 $4$。可以证明没有更优的解。

样例 2

见下发文件中的 summer/summer2.in 与 summer/summer2.ans。

该组样例满足测试点 $4\sim 7$ 的约束条件。

样例 3

见下发文件中的 summer/summer3.in 与 summer/summer3.ans。

该组样例满足测试点 $10\sim 11$ 的约束条件。

样例 4

见下发文件中的 summer/summer4.in 与 summer/summer4.ans。

对于第一组测试数据，其满足特殊性质 A。

对于第二组测试数据，其满足特殊性质 B 和 C。

对于第三组测试数据，其满足特殊性质 B。

对于第四组测试数据，其满足特殊性质 C。

对于第五组测试数据，其满足特殊性质 D。

该组样例满足 $T=5$，$\sum n \le 2\times10^6$。

样例 5

见下发文件中的 summer/summer5.in 与 summer/summer5.ans。

该组样例满足测试点 $23 \sim 25$ 的约束条件。

数据范围

本题共 $25$ 个测试点，每个 $4$ 分。

测试点编号	$\sum n$	特殊性质
$1 \sim 3$	$\le 18$	无
$4 \sim 7$	$\le 100$
$8 \sim 9$	$\le10^3$
$10 \sim 11$	$\le2\times10^5$
$12 \sim 13$	$\le 2 \times 10^6$	A
$14 \sim 15$		B 和 C
$16 \sim 17$		B
$18 \sim 19$		C
$20 \sim 22$		D
$23 \sim 25$		无

特殊性质 A：保证不存在任何一列，使得上下两格为一黑一白。
特殊性质 B：保证不存在任何一列，使得上下两格均为黑色。
特殊性质 C：保证不存在任何一列，使得上下两格均为白色。
特殊性质 D：保证对于任意位置，其颜色在黑白中等概率随机生成。

对于全部数据，保证：$1\le T \le 5$，$1 \le m \le n \le 2\times 10^6$，$\sum{n}\le 2\times10^6$。

下发文件

通过点击此链接下载下发文件。