D. Assigning problems
time limit per test
0.75 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

As a new initiative, the AAPC (Argentine Competitive Programming Association, by its initials in Spanish) aims to organize many contests in a year. Organizing a contest consists of selecting a group of problems of $$$K$$$ different levels numbered from $$$1$$$ to $$$K$$$ in increasing order of difficulty. Moreover, every contest must have exactly $$$C_i$$$ problems assigned to level $$$i$$$ for each $$$i$$$ between $$$1$$$ and $$$K$$$.

In addition to that, each problem has a certain grade of difficulty. If a problem has a grade of difficulty $$$d$$$, it means that the AAPC can assign that problem in a contest in any level greater than or equal to $$$d$$$.

Naturally, the AAPC is not able to repeat problems among different contests, that means that a single problem can only be assigned to a single contest. Moreover, a single problem cannot be assigned to more than one level within the same contest.

The AAPC has requested problem proposals among its members. In total the AAPC has collected $$$P_i$$$ problem proposals with a grade of difficulty equal to $$$i$$$ for each $$$i$$$ between $$$1$$$ and $$$K$$$, and plans to use them to organize as many contests as possible.

Using these problems (not necessarily all of them), what is the maximum number of contests that the AAPC is able to organize?

Input

The first line contains an integer $$$K (1 \leq K \leq 10^5)$$$, which represents the number of different levels in the contests organized by the AAPC.

Then, a second line with $$$K$$$ integers $$$C_1, C_2, \ldots, C_K$$$, where each $$$C_i (1 \leq C_i \leq 10^9)$$$ indicates the number of problems assigned to level $$$i$$$ that a contest organized by the AAPC must have.

Finally, a third line with $$$K$$$ integers $$$P_1, P_2, \ldots, P_K$$$, where $$$P_i (0 \leq P_i \leq 10^9)$$$ denotes the number of problem proposals with a grade of difficulty of $$$i$$$ that the AAPC has at their disposal to create the desired contests.

Output

A single line with an integer that represents the maximum number of contests that the AAPC can organize while attaining the required amount of problems per level using the problems that they have at their disposal.

Examples
Input
5
2 2 2 2 2
100 0 0 0 0
Output
10
Input
5
2 3 2 2 2
10 0 9 3 1
Output
2
Input
5
2 3 2 2 2
0 100 7 0 6
Output
0
Note

In the first example, each contest consists of $$$5$$$ different levels, and $$$2$$$ problems need to be assigned to each level. The AAPC has $$$100$$$ problems at their disposal, each one of them with a grade of difficulty of $$$1$$$, that can be assigned to any level. Hence, the association can organize a maximum of $$$10$$$ contests using those problems.