【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天

原题链接：[https://oier.team/problems/86](https://oier.team/problems/86)。

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$ | $\le 2 \times 10^6$ | B 和 C| | $16 \sim 17$ | $\le 2 \times 10^6$ | B | | $18 \sim 19$ | $\le 2 \times 10^6$ | C | | $20 \sim 22$ | $\le 2 \times 10^6$ | D | | $23 \sim 25$ | $\le 2 \times 10^6$ | 无 | 特殊性质 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$。