Description

Original source: HAOI 2008

In a $4\times 4$ grid, several identical toys are placed. Someone wants to rearrange these toys into their desired state. The rule is that toys can only be moved in the four directions: up, down, left, or right, and the target position must not already contain a toy. Please determine the minimum number of moves required to transform the initial toy arrangement into the target state.

Input Format

The first four lines represent the initial state of the toys. Each line contains $4$ digits, either $1$ or $0$, where $1$ indicates that a toy is placed in the grid cell, and $0$ indicates no toy is placed.
This is followed by a blank line.
The next four lines represent the target state of the toys, with each line containing $4$ digits $1$ or $0$, following the same meaning as above.

Output Format

An integer representing the minimum number of moves required.

Sample 1

1111
0000
1110
0010

1010
0101
1010
0101

4