C1068 [Contest #3]棋盘

内存限制:256 MB 时间限制:1000 ms

题目描述

小猫有一个 $2\times N$ 的棋盘,每一个格子放着一个黑棋子或白棋子。

小熊觉得小猫的棋盘不够好看,想要把棋盘上的一部分白棋子替换成黑棋子,使得所有黑棋子都能够在仅允许上下左右四个方向走,且仅经过黑棋子在的格子的情况下两两互相到达。

小熊想知道至少要将多少个白棋子替换成黑棋子。

注意:不能将黑棋子替换成白棋子。

输入格式

第一行有一个正整数 $N$ ($1 \le N \le 10^5$)。

接下来两行,每行 $N$ 个整数,描述整个棋盘。若第 $i$ 行的第 $j$ 个整数是 $0$,代表棋盘 $(i,j)$ 的位置放着白棋子,若是 $1$ 则放着黑棋子。

数据保证至少存在一个黑棋子。

输出

输出一行包含一个整数,表示答案。

样例

样例输入 1

3 1 0 0 0 0 1

样例输出 1

2

样例输入 2

5 0 1 0 1 0 0 0 1 0 0

样例输出 2

1

提示

样例一中可以将第一行的两个白棋子替换成黑棋子。

样例二中可以将位置 $(1, 3)$ 的白棋子换成黑棋子。