分数: 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