학원의 날짜별 연습 묶음

문제

한 학원은 새 학기의 N일 동안 사용할 연습지를 준비한다. 날짜에는 수업 순서에 따라 1번부터 N번까지 번호가 붙어 있다. 모든 날짜의 연습지가 필요하며, 학원은 인쇄실에서 판매하는 묶음을 골라 준비 비용을 줄이려 한다. 인쇄실에는 두 종류의 묶음이 있다. 하루 묶음은 특정 날짜 i의 연습지만 담고 있으며 가격은 A_i다. 이틀 묶음은 서로 연속한 날짜 i와 i+1의 연습지를 함께 담고 있으며 가격은 B_i다. 이틀 묶음은 1번과 2번 날짜부터 N-1번과 N번 날짜까지 마련되어 있다. N이 1이면 이틀 묶음은 없다. 묶음마다 날짜에 맞춘 서로 다른 해설 번호가 인쇄된다. 따라서 학원은 같은 날짜가 여러 묶음에 중복으로 포함되도록 주문할 수 없다. 모든 날짜가 선택한 묶음 중 정확히 하나에 포함되어야 한다. 예를 들어 어떤 이틀 묶음을 선택했다면 그 두 날짜의 하루 묶음은 선택할 수 없고, 둘 중 한 날짜라도 겹치는 다른 이틀 묶음도 선택할 수 없다. 연속하지 않은 두 날짜를 임의로 묶거나, 이틀 묶음에서 한 날짜의 연습지만 떼어 주문하는 것은 허용되지 않는다. 각 묶음의 가격은 입력에 주어진 그대로이며, 이틀 묶음이 두 하루 묶음보다 저렴하다는 보장은 없다. 가격이 0인 묶음도 일반 묶음과 동일하게 날짜를 차지한다. 학원은 하루 묶음을 모두 선택할 수 있으므로 항상 유효한 주문 방법이 존재한다. 가능한 주문 방법 중 전체 가격의 합이 가장 작은 값을 구한다. 최소 비용을 만드는 주문 방법이 여러 개라면 어느 방법을 택하는지는 구분하지 않으며, 선택한 묶음의 목록이나 개수는 출력하지 않는다. 준비할 날짜가 하루뿐인 경우에도 같은 기준으로 비용을 계산한다.

입력

첫째 줄에 날짜 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
둘째 줄에 하루 묶음의 가격 A_1, ..., A_N이 공백으로 구분되어 주어진다.
N이 2 이상이면 셋째 줄에 이틀 묶음의 가격 B_1, ..., B_(N-1)이 공백으로 구분되어 주어진다. B_i는 i번과 i+1번 날짜를 함께 준비하는 가격이다. N이 1이면 셋째 줄은 주어지지 않는다.
모든 가격은 0 이상 9,999 이하의 정수다.

출력

모든 날짜를 정확히 한 번씩 포함하도록 묶음을 선택하는 데 필요한 최소 비용을 정수 하나로 출력한다.

4
6 9 4 8
10 5 7

17

1
0

0

3
8 8 8
3 3

11

출처: Devin.KR 자체 제작