학원의 연속 복습 자료

문제

한 학원에서 새 복습 과정을 위한 인쇄 자료를 준비하고 있다. 과정에는 1번부터 N번까지 번호가 붙은 수업이 있으며, 학생은 번호 순서대로 모든 수업을 듣는다. 자료 담당자는 각 수업에 필요한 내용을 빠짐없이 제공하면서 전체 인쇄 비용을 가능한 한 작게 만들려고 한다. 이를 위해 한 수업의 내용만 담은 낱권과 연속한 두 수업의 내용을 함께 담은 묶음 중에서 사용할 자료를 고른다. i번 수업의 낱권을 인쇄하는 비용은 A_i이다. i번 수업과 i+1번 수업의 묶음을 인쇄하는 비용은 B_i이다. 묶음은 반드시 번호가 연속한 두 수업을 대상으로 하며, 첫 수업과 마지막 수업을 이어 붙이거나 세 수업 이상을 한 묶음으로 만드는 것은 허용하지 않는다. 각 비용은 해당 자료 한 개를 준비하는 데 필요한 전체 비용이다. 자료를 고를 때 각 수업의 내용은 정확히 한 번 포함되어야 한다. 예를 들어 어떤 묶음을 선택했다면 그 묶음에 들어 있는 두 수업의 낱권을 추가로 고를 수 없다. 또한 선택한 두 묶음이 같은 수업을 공유해서도 안 된다. 수업 내용을 두 번 제공하거나 일부 수업의 내용을 빼는 구성은 사용할 수 없다. 낱권과 묶음을 섞어 고르는 것은 허용된다. 묶음의 비용이 두 낱권의 비용 합보다 항상 싼 것은 아니다. 따라서 묶음을 많이 고르는 것이 반드시 유리하지는 않으며, 한 묶음의 선택이 바로 옆 수업에서 고를 수 있는 자료에도 영향을 준다. 모든 수업의 낱권을 고르는 구성은 언제나 가능하다. 최소 비용을 만드는 구성이 여러 개여도 구성 자체를 구분해 출력할 필요는 없다. 주어진 비용으로 전체 수업을 정확히 한 번씩 포함하는 자료를 준비할 때 필요한 최소 총비용을 구한다.

입력

첫째 줄에 수업 수 N이 주어진다. N은 정수이며 1 ≤ N ≤ 20,000이다.
둘째 줄에 A_1부터 A_N까지 N개의 정수가 주어진다.
N ≥ 2이면 셋째 줄에 B_1부터 B_(N-1)까지 N-1개의 정수가 주어진다. N = 1이면 셋째 줄은 주어지지 않는다.
모든 A_i와 B_i는 1 이상 1,000,000 이하의 정수이다.

출력

가능한 최소 총비용을 정수 하나로 출력한다.

4
6 9 5 8
10 11 9

19

1
7

7

3
8 3 9
20 7

15

출처: Devin.KR 자체 제작