Background

Original problem link: https://oier.team/problems/S4B。

Problem Description

youyou has a $2 \times n$ grid, where each cell may be black or white.

Now youyou and yy are going to play a game on this grid:

• First, youyou chooses a connected component, which is allowed to be empty.
• Then yy may choose at most $m$ columns in the grid, and swap the colors of the upper and lower cells in each chosen column.

A cell set $S$ is called a connected component if and only if any two cells in $S$ can be connected through some cells in $S$ that are edge-adjacent (i.e. 4-connected).

youyou wants to maximize the final value of (the number of black cells minus the number of white cells) inside the connected component, while yy wants to minimize it.

You need to compute: when both players use optimal strategies, what is the final value of (black cells minus white cells) in the connected component?

Input Format

This problem has multiple test cases.

The first line contains two integers $c, T$, representing the subtask ID and the number of test cases. If $c = 0$, this subtask is the sample.

For each test case, the first line contains two integers $n, m$, representing the number of columns in the grid and the number of swap operations.

The next two lines each contain a length-$n$ binary string of $0$ and $1$, describing the colors of the grid. Here, $1$ means a black cell, and $0$ means a white cell.

Output Format

For each test case, output one line with one number, meaning the final value of (black cells minus white cells).

0 2
5 2
11110
01001
7 1
1110000
0001111

2
4

Hint

[Sample Explanation #1]

In the following, $(x, y)$ denotes the cell in row $x$ and column $y$.

For the first test case, youyou chooses the two cells $(1,2)$ and $(2,2)$. No matter how yy swaps, the difference between the number of black cells and the number of white cells is at least $2$. It can be proven that there is no better solution.

For the second test case, youyou chooses the eight cells $(1,1),(1,2),(1,3),(1,4),(2,4),(2,5),(2,6),(2,7)$. No matter how yy swaps, the difference between the number of black cells and the number of white cells is at least $4$. It can be proven that there is no better solution.

[Sample #2]

See the attached files summer/summer2.in and summer/summer2.ans.

This sample satisfies the constraints of subtasks $4\sim 7$.

[Sample #3]

See the attached files summer/summer3.in and summer/summer3.ans.

This sample satisfies the constraints of subtasks $10\sim 11$.

[Sample #4]

See the attached files summer/summer4.in and summer/summer4.ans。

For the first test case, it satisfies special property A.

For the second test case, it satisfies special properties B and C.

For the third test case, it satisfies special property B.

For the fourth test case, it satisfies special property C.

For the fifth test case, it satisfies special property D.

This sample satisfies $T = 5$ and $\sum n \le 2\times10^6$.

[Sample #5]

See the attached files summer/summer5.in and summer/summer5.ans。

This sample satisfies the constraints of subtasks $23 \sim 25$.

[Constraints]

This problem has $25$ subtasks, each worth $4$ points.

Special property A: it is guaranteed that there is no column where the upper and lower cells are one black and one white.
Special property B: it is guaranteed that there is no column where both cells are black.
Special property C: it is guaranteed that there is no column where both cells are white.
Special property D: it is guaranteed that for any position, its color is generated randomly with equal probability of being black or white.

For all testdata, it is guaranteed that $1\le T \le 5$, $1 \le m \le n \le 2\times 10^6$, and $\sum n \le 2\times10^6$。

Translated by ChatGPT 5