33754번 - 격자 막기 서브태스크

문제

여러분에게 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ドル$이 적혀 있습니다.

서브태스크

힌트