시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB115840130139.295%

문제

여러분에게 $2\times N$ 격자가 주어집니다. 이때 이 격자에서 $i$행 $j$열의 칸을 $(i, j)$로 표시합니다. 격자의 각 칸에는 $0$ 또는 $1$의 숫자가 적혀 있습니다.

이때, $(1,1)$에서 상하좌우로 인접한 칸으로 이동하는 것만을 반복하여 $(2,N)$으로 이동하는 방법 중 $1$이 적힌 칸만 지나가는 방법이 없는 경우, 격자가 막혀 있다고 합니다.

여러분은 다음 연산을 가능한 한 적은 횟수로 사용하여 격자를 막혀 있는 상태로 만들어야 합니다.

  • $(1, 1)$과 $(2, N)$을 제외한 칸들 중 $1$이 적힌 한 칸을 골라 $1$을 지우고 $0$을 새로 적습니다.

격자를 막혀 있는 상태로 만들기 위해 필요한 연산의 최소 횟수를 구하는 프로그램을 작성해 주세요.

입력

첫 번째 줄에 정수 $N$이 주어집니다.

두 번째 줄에는 격자의 첫 번째 행에 적힌 $N$개의 정수가 공백으로 구분되어 주어집니다. 다시 말해, 그중 $k$번째 정수는 $(1,k)$에 적힌 정수와 같습니다.

세 번째 줄에는 격자의 두 번째 행에 적힌 $N$개의 정수가 공백으로 구분되어 주어집니다. 다시 말해, 그중 $k$번째 정수는 $(2,k)$에 적힌 정수와 같습니다.

출력

한 줄에 격자를 막혀 있는 상태로 만들기 위해 필요한 연산의 최소 횟수를 출력하세요.

제한

  • $3 \le N \le 100\ 000$
  • $(1, 1)$와 $(2, N)$에는 모두 $1$이 적혀 있습니다.

서브태스크

번호배점제한
15

$N = 3$

212

모든 $1 \le k \le N$에 대하여, $(1,k)$와 $(2,k)$에는 같은 정수가 적혀 있습니다.

362

주어진 격자는 막혀 있는 상태가 아닙니다.

421

추가 제약 조건이 없습니다.

예제 입력 1

5
1 0 1 1 1
1 1 1 0 1

예제 출력 1

1

예제 입력 2

5
1 0 0 1 1
1 1 1 0 1

예제 출력 2

0

채점 및 기타 정보

  • 예제는 채점하지 않는다.