반납 도서 스캔 묶음

문제

도서관의 반납 처리대에는 책 N권이 한 줄로 놓여 있다. 책에는 현재 놓인 순서대로 1번부터 N번까지 번호가 붙어 있다. 반납 처리 장치는 각 책의 식별 정보와 표지 상태를 스캔해야 하며, 모든 책을 정확히 한 번씩 처리한 뒤 작업을 마쳐야 한다. 장치는 한 번에 책 한 권을 처리하거나, 현재 줄에서 서로 이웃한 두 권을 함께 처리할 수 있다. 작업 중에 책의 순서를 바꾸거나 다른 위치로 옮길 수는 없다. 이를 작업 계획의 관점에서 보면, 처음 주어진 책의 줄을 길이가 1 또는 2인 연속한 묶음들로 나누는 것이다. 각 책은 정확히 하나의 묶음에 속해야 하고, 서로 다른 묶음이 같은 책을 포함할 수는 없다. 세 권 이상을 한 묶음으로 처리하는 기능은 없다. 책 i를 혼자 처리하는 데 필요한 시간은 A_i다. 책 i와 책 i+1을 한 묶음으로 처리하는 데 필요한 시간은 B_i다. 두 권을 함께 처리할 때는 B_i만 사용하며, 그 두 책의 A 값을 추가로 더하지 않는다. 함께 처리하는 시간은 두 책의 두께나 표지 조합에 따라 달라진다. 따라서 B_i가 A_i와 A_{i+1}의 합보다 작을 수도 있고, 같거나 클 수도 있다. 입력으로 주어진 값 외에 별도의 준비 시간이나 묶음 사이의 전환 시간은 없다. 장치는 한 번에 한 묶음만 처리하므로 전체 작업 시간은 선택한 모든 묶음의 처리 시간을 더한 값이다. 일부 책은 사전 확인이 끝나 처리 시간이 0일 수 있으며, 두 권 묶음의 시간도 0일 수 있다. 시간이 0인 경우에도 해당 책을 처리하는 묶음은 반드시 계획에 포함해야 한다. 예를 들어 네 권의 책은 네 권을 각각 처리하거나, 앞의 두 권과 뒤의 두 권을 각각 묶거나, 가운데 두 권만 묶고 양 끝을 따로 처리할 수 있다. 반면 1번과 3번 책을 묶는 계획은 허용되지 않는다. 가능한 모든 작업 계획 중 전체 작업 시간이 가장 짧은 계획의 시간을 구한다. 최적 계획이 여러 개여도 계획 자체는 출력하지 않는다.

입력

첫째 줄에 책의 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
N이 2 이상이면 셋째 줄에 정수 B_1, B_2, ..., B_{N-1}이 공백으로 구분되어 주어진다. N이 1이면 셋째 줄은 주어지지 않는다.
모든 A_i와 B_i는 0 이상 1,000,000 이하의 정수이며, 시간의 단위는 밀리초다.

출력

모든 책을 정확히 한 번씩 처리하는 데 필요한 전체 작업 시간의 최솟값을 밀리초 단위 정수로 출력한다. 최적 계획이 여럿이어도 최솟값 하나만 출력한다.

5
6 8 3 7 4
9 20 5 8

18

1
0

0

4
5 5 5 5
20 1 20

11

출처: Devin.KR 자체 제작