Why Did the Cow Cross the Road 8

Time limit2sMemory limit512 MB

Summary

Two rows each hold a permutation of N breeds; pair friendly pastures across the road without crossings to maximize the number of crosswalks.

Level: Medium7 of 10
Topics: Dynamic programming, Intervals, Sorting
Solved: No attempts yet

Problem

Farmer John (a different John from the one we have been helping so far) has $N$ breeds of cows on his farm, numbered breed 1, breed 2, ..., breed $N$ ( $1 \le N \le 1000$ ). Cows of breed $a$ and breed $b$ are friendly if $|a-b| \le 4$ , and unfriendly otherwise.

A straight road runs through the farm, with $N$ pastures on each side. Each pasture on the left side holds one breed of cow, and every breed appears in exactly one left pasture. The right side is arranged the same way. To prevent traffic accidents, John wants to build crosswalks. Each crosswalk connects one pasture on the left side to one pasture on the right side, and it does not have to be perpendicular to the road. A crosswalk may only connect two pastures whose cows are friendly. Each pasture may have at most one crosswalk, and no two crosswalks may cross each other.

Find the maximum number of crosswalks John can build.

Input

The first line contains $N$ . Each of the next $N$ lines gives the breed number of the cows in the pastures on the left side of the road, in order. Every breed appears exactly once. The following $N$ lines describe the pastures on the right side of the road in the same way.

Output

Print the maximum number of crosswalks that can be built under these rules.

Examples1

Example 1
Input
```
6
1
2
3
4
5
6
6
5
4
3
2
1
```
Expected output
```
5
```