페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2491

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

버거
서브태스크
1초 1024MB

문제

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

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

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

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


입력

첫 줄에 정수 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)


출력

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


부분문제

번호 점수 조건
#19점

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

#217점

 n, x[i] ≤ 100

#325점

 n, x[i] ≤ 1500

#449점

추가 제한 없음


예제 #1

3
14 10 100
3 1 1
2 3 1
5

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


예제 #2

2
83 72
1 3
1 3
24
로그인해야 코드를 작성할 수 있어요.