A - 答案の採点 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は N 問からなるマークシート式のテストを受けました。各問題の解答は 0 または 1 のいずれかです。

高橋君の解答は長さ N の文字列 S で表されます。S の i 文字目が 1 ならば i 番目の問題に 1 と解答したことを、0 ならば 0 と解答したことを意味します。同様に、正解は長さ N の文字列 T で表されます。

高橋君は解答を提出する前に見直しをして、S の 0 個以上の文字を書き換えることで、不正解の問題数を K 問以下にしたいと考えています。

具体的には、S の各文字について、その文字を 0 から 1 に、または 1 から 0 に変更するか、そのままにするかを選びます。こうして得られた長さ N の文字列を S' とします。

  • S' の i 文字目と T の i 文字目が異なるような i （1 \leq i \leq N）の個数を不正解の問題数と呼びます。
  • S の i 文字目と S' の i 文字目が異なるような i （1 \leq i \leq N）の個数を書き換え回数と呼びます。

不正解の問題数が K 以下となるような S' は少なくとも 1 つ存在します（例えば S' = T とすれば不正解は 0 問です）。そのような S' の中での書き換え回数の最小値を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 0 \leq K \leq N
  • N, K は整数
  • S は 0 と 1 のみからなる長さ N の文字列
  • T は 0 と 1 のみからなる長さ N の文字列

入力

N K
S
T
  • 1 行目には、問題数を表す整数 N と、許容される不正解数の上限を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、高橋君の解答を表す長さ N の文字列 S が与えられる。
  • 3 行目には、正解を表す長さ N の文字列 T が与えられる。

出力

不正解の問題数を K 問以下にするために必要な書き換え回数の最小値を 1 行で出力せよ。

入力例 1

5 2
10100
01010

出力例 1

2

入力例 2

5 3
11001
10011

出力例 2

0

入力例 3

20 5
11111111110000000000
11111000001111100000

出力例 3

5

入力例 4

50 10
11010011100101101001110010011101010011100101101001
00101100011010010110001101100010101100011010010110

出力例 4

40

入力例 5

1 0
0
1

出力例 5

1

Score : 233 pts

Problem Statement

Takahashi took a multiple-choice test consisting of N questions. The answer to each question is either 0 or 1.

Takahashi's answers are represented by a string S of length N. If the i-th character of S is 1, it means he answered 1 for the i-th question; if it is 0, it means he answered 0. Similarly, the correct answers are represented by a string T of length N.

Before submitting his answers, Takahashi wants to review and rewrite 0 or more characters of S so that the number of incorrect answers is at most K.

Specifically, for each character of S, he chooses whether to change it from 0 to 1, from 1 to 0, or leave it as is. Let S' be the string of length N obtained in this way.

  • The number of indices i (1 \leq i \leq N) such that the i-th character of S' and the i-th character of T differ is called the number of incorrect answers.
  • The number of indices i (1 \leq i \leq N) such that the i-th character of S and the i-th character of S' differ is called the number of rewrites.

There exists at least one S' such that the number of incorrect answers is at most K (for example, setting S' = T gives 0 incorrect answers). Find the minimum number of rewrites among all such S'.

Constraints

  • 1 \leq N \leq 10^6
  • 0 \leq K \leq N
  • N, K are integers
  • S is a string of length N consisting only of 0 and 1
  • T is a string of length N consisting only of 0 and 1

Input

N K
S
T
  • The first line contains an integer N representing the number of questions and an integer K representing the upper limit on the number of allowed incorrect answers, separated by a space.
  • The second line contains a string S of length N representing Takahashi's answers.
  • The third line contains a string T of length N representing the correct answers.

Output

Print in one line the minimum number of rewrites needed to make the number of incorrect answers at most K.

Sample Input 1

5 2
10100
01010

Sample Output 1

2

Sample Input 2

5 3
11001
10011

Sample Output 2

0

Sample Input 3

20 5
11111111110000000000
11111000001111100000

Sample Output 3

5

Sample Input 4

50 10
11010011100101101001110010011101010011100101101001
00101100011010010110001101100010101100011010010110

Sample Output 4

40

Sample Input 5

1 0
0
1

Sample Output 5

1