#P1700F. Puzzle

Puzzle

Description

Pupils Alice and Ibragim are best friends. It's Ibragim's birthday soon, so Alice decided to gift him a new puzzle. The puzzle can be represented as a matrix with 22 rows and nn columns, every element of which is either 00 or 11. In one move you can swap two values in neighboring cells.

More formally, let's number rows 11 to 22 from top to bottom, and columns 11 to nn from left to right. Also, let's denote a cell in row xx and column yy as (x,y)(x, y). We consider cells (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2) neighboring if x1x2+y1y2=1|x_1 - x_2| + |y_1 - y_2| = 1.

Alice doesn't like the way in which the cells are currently arranged, so she came up with her own arrangement, with which she wants to gift the puzzle to Ibragim. Since you are her smartest friend, she asked you to help her find the minimal possible number of operations in which she can get the desired arrangement. Find this number, or determine that it's not possible to get the new arrangement.

The first line contains an integer nn (1n2000001 \leq n \leq 200\,000) — the number of columns in the puzzle.

Following two lines describe the current arrangement on the puzzle. Each line contains nn integers, every one of which is either 00 or 11.

The last two lines describe Alice's desired arrangement in the same format.

If it is possible to get the desired arrangement, print the minimal possible number of steps, otherwise print 1-1.

Input

The first line contains an integer nn (1n2000001 \leq n \leq 200\,000) — the number of columns in the puzzle.

Following two lines describe the current arrangement on the puzzle. Each line contains nn integers, every one of which is either 00 or 11.

The last two lines describe Alice's desired arrangement in the same format.

Output

If it is possible to get the desired arrangement, print the minimal possible number of steps, otherwise print 1-1.

Samples

样例输入 1

5
0 1 0 1 0
1 1 0 0 1
1 0 1 0 1
0 0 1 1 0

样例输出 1

5

样例输入 2

3
1 0 0
0 0 0
0 0 0
0 0 0

样例输出 2

-1

Note

In the first example the following sequence of swaps will suffice:

  • (2,1),(1,1)(2, 1), (1, 1),
  • (1,2),(1,3)(1, 2), (1, 3),
  • (2,2),(2,3)(2, 2), (2, 3),
  • (1,4),(1,5)(1, 4), (1, 5),
  • (2,5),(2,4)(2, 5), (2, 4).

It can be shown that 55 is the minimal possible answer in this case.

In the second example no matter what swaps you do, you won't get the desired arrangement, so the answer is 1-1.