Page not loading? Try clicking here.
Placeholder

#2491

[중등부] 2025 KOI 1차대회 대비 모의고사 (2주차)

버거
Subtask
1s 1024MB

Problems

새로운 프랜차이즈 버거 가게 "정올 버거"가 드디어 오픈했다.

정올 버거에서는 총 n가지의 재료를 사용하는데, 각각 1번부터 n번까지 번호를 붙여 관리한다. 이 때, 재료 i는 x[i]개 있다.

정올 버거에서는 버거를 만들기 위한 두 가지 레시피가 있는데, 첫 번째 레시피는 a[i]개, 두 번째 레시피는 b[i]개의 재료 i를 필요로 한다.

정올 버거가 매출을 극대화하기 위해 현재 가진 재료들로 최대한 만들 수 있는 버거의 수를 출력하는 프로그램을 작성하자.


Input

첫 줄에 정수 n이 주어진다. (1 ≤ n ≤ 100\,000)

두 번째 줄에 n개의 정수 x[1], x[2],\ \dots\ , x[n]가 주어진다. (1 ≤ x[i] ≤ 10^9)

세 번째 줄에 n개의 정수 a[1], a[2],\ \dots\ , a[n]가 주어진다. (1 ≤ a[i] ≤ 10^9)

네 번째 줄에 n개의 정수 b[1], b[2],\ \dots\ , b[n]가 주어진다. (1 ≤ b[i] ≤ 10^9)


Output

현재 가진 재료들로 최대한 만들 수 있는 버거의 수를 출력한다.


Subtask

# Score Condition
#19

 a[i] = b[i] (두 레시피가 같음)

#217

 n, x[i] ≤ 100

#325

 n, x[i] ≤ 1500

#449

추가 제한 없음


Example #1

3
14 10 100
3 1 1
2 3 1
5

첫 번째 레시피로 3개, 두 번째 레시피로 2개를 만드는 것이 가능하다.


Example #2

2
83 72
1 3
1 3
24
You must sign in to write code.