Two Movies
Contest: Educational Codeforces Round 167 (Rated for Div. 2)
Difficulty rating: 1400
Tags: greedy, math

A movie company has released $$$2$$$ movies. These $$$2$$$ movies were watched by $$$n$$$ people. For each person, we know their attitude towards the first movie (liked it, neutral, or disliked it) and towards the second movie.

If a person is asked to leave a review for the movie, then:

- if that person liked the movie, they will leave a positive review, and the movie's rating will increase by $$$1$$$;
- if that person disliked the movie, they will leave a negative review, and the movie's rating will decrease by $$$1$$$;
- otherwise, they will leave a neutral review, and the movie's rating will not change.

Every person will review exactly one movie — and for every person, you can choose which movie they will review.

The company's rating is the minimum of the ratings of the two movies. Your task is to calculate the maximum possible rating of the company.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-1 \le a_i \le 1$$$), where $$$a_i$$$ is equal to $$$-1$$$ if the first movie was disliked by the $$$i$$$-th viewer; equal to $$$1$$$ if the first movie was liked; and $$$0$$$ if the attitude is neutral.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-1 \le b_i \le 1$$$), where $$$b_i$$$ is equal to $$$-1$$$ if the second movie was disliked by the $$$i$$$-th viewer; equal to $$$1$$$ if the second movie was liked; and $$$0$$$ if the attitude is neutral.

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single integer — the maximum possible rating of the company, if for each person, choose which movie to leave a review on.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
2
-1 1
-1 -1
1
-1
-1
5
0 -1 1 0 1
-1 1 0 0 1
4
-1 -1 -1 1
-1 1 1 1

Example output:
0
-1
1
1

Editorial:
Let's notice an important fact: if $$$a_i \ne b_i$$$, it is always optimal to choose a review for the movie with the better rating: taking the worse option doesn't increase the rating of any movie.
Using this fact, let's calculate several values:
• $$$x$$$ — the rating of the first movie among people who liked the first movie more than the second one ($$$a_i > b_i$$$);
• $$$y$$$ — the rating of the second movie among people who liked the second movie more than the first one ($$$b_i > a_i$$$);
• $$$neg$$$ — the number of people who didn't like either movie;
• $$$pos$$$ — the number of people who liked both movies.
Now we have to distribute the reviews of the viewers having $$$a_i=b_i$$$. To do this, we can iterate the contribution of such viewers to the rating of the first movie (denoted as $$$i$$$) from $$$-neg$$$ to $$$pos$$$. Then, the final rating of the first movie is $$$x+i$$$, and the final rating of the second movie is $$$y+(pos-neg-i)$$$. Among all the options, choose the one where the minimum of these two values is maximized.