King's Decree (Problem K, CS3233 Midterm Contest 2023, 2023)
Time limit: 1 sec
Memory limit: 1024 MB

# Problem Statement
> **SoCCat the Cat King is a very fair cat. Currently, SoCCat wants to ensure all cats can live in peace and harmony!**

The Cat Kingdom is a very large kingdom, with $n$ cats living in it. The cats are numbered from $1$ to $n$.

King SoCCat has noticed a glaring problem in the kingdom — the uneven distribution of wealth among the cats. To solve this problem, King SoCCat has decreed that wealthy cats should give some of their wealth to poorer cats — to ensure that all cats can live in peace and harmony.

After surveying each cat in the kingdom, King SoCCat has determined that:

* Cat $i$ has $w_i$ units of wealth.  
* Cat $i$ is not willing to have less than $l_i$ ($l_i \le w_i$) units of wealth.

As a fair king, SoCCat wants to ensure that all cats have **at least** $l_i$ units of wealth, and the poorest cat has the maximum possible wealth.

To achieve this, King SoCCat can do the following any number of times:

* Choose a cat $i$ with wealth **strictly greater** than $l_i$.  
* Choose any other cat $j$, and give $1$ unit of wealth from cat $i$ to cat $j$.

Unfortunately, King SoCCat is not very good at math. Therefore, as a friend of the Cat Kingdom, help King SoCCat!

# Input

The input starts with a line containing an integer $C$, denoting the number of test cases ($1 \le C \le 300\,000$). Each test case has the following format.

* The first line contains an integer $n$, denoting the number of cats in the kingdom ($1 \le n \le 300\,000$). The sum of $n$ over all test cases does not exceed $300\,000$.  
* The second line contains $n$ integers $w_1, w_2, \dots, w_n$, denoting the wealth of each cat ($1 \le w_i \le 10^9$).  
* The third line contains $n$ integers $l_1, l_2, \dots, l_n$, denoting the minimum wealth that each cat is willing to have ($1 \le l_i \le w_i$).

# Output

For each test case, output a single integer denoting the maximum possible wealth that the poorest cat can have, if King SoCCat distributes the wealth of the cats in the kingdom fairly and optimally.

# Sample Input #1
```
2
5
4 2 3 6 12
3 2 3 3 10
8
998 244 353 3109 4650 4305 6507 9699
100 200 300 2040 4230 4236 5234 3233
```
# Sample Output #1
```
4
3233
```

Sample inputs:
2
5
4 2 3 6 12
3 2 3 3 10
8
998 244 353 3109 4650 4305 6507 9699
100 200 300 2040 4230 4236 5234 3233

Sample outputs:
4
3233

# Solution Analysis

Note that we want to maximize the minimum value – hence, let’s try to binary search the answer. Suppose we want to test whether every cat can have at least $\lambda$ wealth. If $w_i \leq \lambda$, then cat $i$ needs $\lambda - w_i$ wealth. If $w_i > \lambda$, then cat $i$ can donate $w_i - \max\{l_i, \lambda\}$ wealth. We simply check if the amount of wealth which can be donated is greater than or equal to the amount of wealth that is needed. In other words, whether
$$
\sum \max\{0, \lambda - w_i\} \leq \sum \max\{0, w_i - \max\{l_i, \lambda\}\}.
$$

Special judge (C++ scorer):