Burgers

Interview

Time limit1sMemory limit1024 MB

Summary

Given stock x_i and the per-ingredient needs a_i and b_i of two burger recipes, find the maximum number of burgers that can be made.

Level: Medium5 of 10
Topics: Binary search, Math, Greedy
Solved: No attempts yet

Problem

Kai the lobster is starting a burger chain. He has $n$ ingredients, labelled from $1$ to $n$ . For each ingredient $i$ , he has $x_i$ portions of ingredient $i$ .

He has two recipes for burgers. For each ingredient $i$ , the first recipe requires $a_i$ portions of ingredient $i$ , and the second recipe requires $b_i$ portions of ingredient $i$ .

Find the maximum total number of burgers Kai can make.

Input

The first line contains one integer $n$ , the number of different ingredients.

The second line contains $n$ integers $x_1, x_2, \dots, x_{n-1}, x_n$ , the total number of portions Kai has of each ingredient.

The third line contains $n$ integers $a_1, a_2, \dots, a_{n-1}, a_n$ , the number of portions of each ingredient for the first recipe.

The fourth line contains $n$ integers $b_1, b_2, \dots, b_{n-1}, b_n$ , the number of portions of each ingredient for the second recipe.

Output

Output a single integer on a single line, the largest number of burgers Kai can make.

Constraints

$1 \le n \le 100\,000$

$1 \le x_i, a_i, b_i \le 10^9$

Examples2

Example 1
Input
```
3
14 10 100
3 1 1
2 3 1
```
Expected output
```
5
```
Example 2
Input
```
2
83 72
1 3
1 3
```
Expected output
```
24
```