도서관 표지 보수 작업

문제

도서관의 보수 담당자가 표지가 낡은 책 N권을 작업대에 늘어놓았다. 책에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 책마다 표지의 재질과 손상 정도가 달라서 보수 비용도 서로 다르다. 담당자는 책을 한 권씩 보수하거나, 작업대에서 원래 이웃한 두 권을 함께 보수할 수 있다. 책 i번을 혼자 보수하면 비용 A_i가 든다. 책 i번과 i+1번을 함께 보수하면 두 책을 모두 보수하는 데 비용 B_i가 든다. 함께 보수하는 비용에는 두 책의 작업 비용이 모두 포함되어 있으므로 A_i나 A_(i+1)을 추가로 내지 않는다. 두 권의 재질이 잘 맞으면 함께 작업하는 편이 저렴할 수 있지만, 그렇지 않으면 두 권을 따로 보수하는 편이 더 저렴할 수도 있다. 모든 책은 정확히 한 작업에 포함되어야 한다. 따라서 어떤 책을 두 권짜리 작업에 포함했다면 그 책을 한 권짜리 작업이나 다른 두 권짜리 작업에 다시 포함할 수 없다. 세 권 이상을 한 작업으로 묶는 방식은 허용하지 않는다. 두 권을 묶을 때의 이웃 관계는 처음 붙어 있던 번호만으로 판단한다. 예를 들어 중간 책의 보수가 끝났더라도 번호가 두 칸 이상 차이 나는 책을 새롭게 이웃한 것으로 취급하지 않는다. 작업을 실행하는 순서에는 제한이 없으며, 순서에 따라 비용이 달라지지 않는다. 전체 비용은 선택한 모든 작업의 비용을 더한 값이다. 담당자는 모든 책을 빠짐없이 보수하면서 이 전체 비용을 가장 작게 만들려고 한다. 입력에는 모든 한 권짜리 작업 비용과 모든 이웃한 두 권짜리 작업 비용이 주어진다. 필요한 전체 비용의 최솟값을 구한다. 최소 비용을 만드는 작업 구성이 여러 개이면 구성 자체를 구분할 필요가 없으며, 최솟값만 출력한다. 한 권짜리 작업은 모든 책에 허용되므로 작업을 완료할 수 없는 경우는 없다.

입력

첫째 줄에 책의 수 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
둘째 줄에 A_1부터 A_N까지 정수 N개가 공백으로 구분되어 주어진다.
N이 2 이상이면 셋째 줄에 B_1부터 B_(N-1)까지 정수 N-1개가 공백으로 구분되어 주어진다. N이 1이면 셋째 줄은 주어지지 않는다.
모든 비용은 1 이상 1,000,000 이하의 정수다.

출력

모든 책을 정확히 한 번씩 보수하는 데 필요한 전체 비용의 최솟값을 정수 하나로 출력한다.

5
4 7 3 8 5
6 4 7 6

14

1
9

9

4
2 8 8 2
9 3 9

7

출처: Devin.KR 자체 제작