Description

There are $N$ boys and $N$ girls at a dance party, and we know their heights. Each person can dance with at most one partner.

Each boy either wants to dance with a girl taller than him, or with a girl shorter than him. Similarly, each girl either wants to dance with a boy taller than her, or with a boy shorter than her. No boy and girl of the same height want to dance with each other.

If everyone’s wishes are respected, find the maximum number of dancing pairs.

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain an integer $A_i$. The absolute value of $A_i$ is the height of the $i$-th boy. If $A_i$ is positive, it means the $i$-th boy wants to dance with a girl taller than him; if $A_i$ is negative, it means the $i$-th boy wants to dance with a girl shorter than him.

The next $N$ lines each contain an integer $B_j$. The absolute value of $B_j$ is the height of the $j$-th girl. If $B_j$ is positive, it means the $j$-th girl wants to dance with a boy taller than her; if $B_j$ is negative, it means the $j$-th girl wants to dance with a boy shorter than her.

Output Format

Output one line with one integer, the maximum number of dancing pairs.

1
-1800
1800

0

1
1700
-1800

1

2
-1800 -2200
1900 1700

2

Hint

Constraints

For $100\%$ of the testdata, $1 \le N \le 10^5$, $1500 \le |A_i,B_j| \le 2500$.

Notes

The score setting of this problem follows the original COCI problem, with a full score of $110$.

Translated from COCI2011-2012 CONTEST #1 T4 PLES.

Translated by ChatGPT 5