Grid Game on a 2×n Board

You are given a 2×n grid. Each cell is colored either black or white. Two players, youyou and yy, play the following game on the grid:

1. youyou selects a (possibly empty) connected block of cells. A set of cells S is called a connected block if for any two cells in S there exists a path within S connecting them by adjacent (up, down, left, right) moves.
2. Afterwards, yy chooses at most m columns and in each selected column, swaps the colors of the two cells (i.e. exchanges the top and bottom cell colors).

After these moves, consider the connected block S chosen by youyou. Its score is defined as the difference between the number of black cells and the number of white cells in S after yy’s swaps. The two players act optimally: youyou wants to maximize the final score while yy wants to minimize it.

You are given the initial grid and the integer m. Determine the final score (i.e. the value of black cells minus white cells in the block S) under optimal play.

Game Details and Observations:

• The grid has 2 rows and n columns. Let the colors be represented as follows: black is denoted by 'B' and white by 'W'.
• When youyou chooses the connected block S, he decides for each column whether to include none, one or both cells. However, the block must be connected (cells in consecutive columns must be adjacent via a cell in the same row or by including both cells in one column to switch rows).
• After S is chosen, yy can swap the colors in at most m columns. A column’s swap only affects S if S contains exactly one cell from that column. In a column chosen with a single cell, the two possible outcomes are:

Assume in a given column j the top cell has value a_j and the bottom cell has value b_j, where we assign +1 for black and -1 for white.

• If youyou selects both cells (we denote this option "TB"), the score contribution is c_j = a_j + b_j. Note that swapping this column has no effect since the two cells exchange places.
• If youyou selects a single cell from column j, he can choose the cell with the higher initial value, i.e. max(a_j, b_j). However, yy may swap the column if it reduces the score. After swapping the single cell column, the outcome becomes min(a_j, b_j).

This leads to a key observation per column:

• For a column where both cells are black (B,B): a_j = 1, b_j = 1. Then, selecting both gives 2 while selecting one yields 1 (and swapping has no effect).
• For a column where both cells are white (W,W): a_j = -1, b_j = -1. Then, selecting both gives -2 while selecting one yields -1.
• For a mixed column (B,W or W,B): Selecting both gives 0, while selecting a single cell would yield 1 if not swapped and -1 if swapped. The potential benefit for youyou in a mixed column comes from not swapping (yielding +1) but yy can force a swap (yielding -1) with a cost difference of 2. However, yy can swap at most m columns overall in S.

Thus, for each column, one can consider two main options:

• TB Option:
  • For (B,B): score = 2.
  • For (W,W): score = -2 (but youyou can improve it by taking a single white cell yielding -1).
  • For mixed columns: score = 0.
• Singleton Option (S):
  • For (B,B): score = 1.
  • For (W,W): score = -1.
  • For mixed columns: if chosen as S, yy can decide to swap. If yy uses a swap in that column, the score becomes -1; otherwise it is +1. Since all mixed columns have an identical impact (difference of 2), yy will use his limited budget of m swaps on the singleton choices in mixed columns if beneficial.

Because the block S must be connected (i.e. contiguous in columns with appropriate choices to maintain connectivity), the optimal strategy for youyou is to choose some contiguous interval of columns and in each column choose the option that maximizes his eventual score after yy uses his swaps optimally. In particular, note that for a set of mixed columns in the interval, if the total count is x then yy can swap at most min(x, m) of them. Thus, the total contribution from the mixed columns in the interval becomes:

F(x) = { 0 if x ≤ m, x - 2·m if x > m }.

The contributions from the other columns are additive. Define for each column j:

• If column j is (B,B): contribution = 2.
• If column j is (W,W): contribution = -1 (choosing the singleton option is best).
• If column j is mixed: treat it separately.

Let A_j be defined as follows:

Aj =
  2   if column j is (B,B)   
 -1   if column j is (W,W)   
  0   if column j is mixed

Let M_j = 1 if column j is mixed, and 0 otherwise. Then for any contiguous interval [i, j] the final score is:

Total = (sum of A_k for k from i to j) + F( sum of M_k for k from i to j )

Your task is to find the maximum score that youyou can guarantee (remember that he is allowed to choose an empty block, which gives a score of 0) when both players play optimally.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ N, 0 ≤ m ≤ n), where n is the number of columns and m is the maximum number of columns yy can swap.

The next two lines each contain a string of length n. The first string represents the colors of the top row and the second the colors of the bottom row. Each character is either 'B' (black) or 'W' (white).

outputFormat

Output a single integer, the final score (number of black cells minus number of white cells in the block S) under optimal play by both players.

sample

1 1
B
W

0