← 返回题目列表

AtCoder · awc0033_a

A. 对答题纸评分

中文机器翻译题面 查看原题

分数: 233 分

问题陈述

Takahashi 参加了一项多项选择测试,包括 N 问题。每个问题的答案是 0 or 1.

高桥的答案用字符串表示 S 长度 N。如果 i- 第一个字符 S is 1,表示他回答了 1 为 i第一个问题;如果是的话 0,表示他回答了 0。同样,正确答案用字符串表示 T 长度 N.

在提交答案之前,高桥想回顾并重写 0 或更多字符 S 使得错误答案的数量最多为 K.

具体来说,对于每个字符 S,他选择是否更改为 0 to 1,来自 1 to 0,或保持原样。让 S' 是长度的字符串 N 这样得到。

  • 索引数量 i (1 \leq i \leq N)这样 i- 第一个字符 S' 和 i- 第一个字符 T 不同称为 错误答案数.
  • 索引数量 i (1 \leq i \leq N)这样 i- 第一个字符 S 和 i- 第一个字符 S' 不同称为 重写次数.

至少存在一个 S' 使得错误答案的数量最多为 K (例如,设置 S' = T 给出 0 错误答案)。找出所有此类中的最小重写次数 S'.

约束

  • 1 \leq N \leq 10^6
  • 0 \leq K \leq N
  • N, K 是整数
  • S 是一个长度为的字符串 N 仅包含 0 和 1
  • T 是一个长度为的字符串 N 仅包含 0 和 1

输入

N K
S
T
  • 第一行包含一个整数 N 代表问题数量和一个整数 K 代表允许的错误答案数量上限,以空格分隔。
  • 第二行包含一个字符串 S 长度 N 代表高桥的答案。
  • 第三行包含一个字符串 T 长度 N 代表正确答案。

输出

在一行中打印出最多错误答案所需的最少重写次数 K.


示例输入 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