Burgers

시간 제한1초메모리 제한1024 MB

요약

n개 재료의 보유량과 두 레시피의 재료 소요량이 주어질 때 만들 수 있는 버거 총 개수의 최댓값을 구한다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

Kai the lobster is starting a burger chain selling burgers. He has $n$ ingredients to work with, which are 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 ingredients $i$ .

Can you help Kai compute the maximum total number of burgers he can make?

입력

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

The second line consists of $n$ spaced integers $x\[1], x\[2], \dots , x\[n - 1], x\[n]$ , the total number of portions Kai has of each ingredient.

The third line consists of $n$ spaced 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 consists of $n$ spaced integers $b\[1], b\[2], \dots , b\[n - 1], b\[n]$ , the number of portions of each ingredient for the second recipe.

출력

The output should contain a single integer on a single line, the largest number of burgers Kai can make.

제한

$1 ≤ n ≤ 100\\,000$
$1 ≤ x\[i], a\[i], b\[i] ≤ 10^9$

예제2

예제 1
입력
```
3
14 10 100
3 1 1
2 3 1
```
예상 출력
```
5
```
예제 2
입력
```
2
83 72
1 3
1 3
```
예상 출력
```
24
```