배달 묶음의 정산 비용

문제

배달 앱은 한 구역에서 접수된 N개의 주문을 접수 순서대로 정산하려고 한다. 주문에는 1번부터 N번까지 번호가 붙어 있다. 정산 서버는 주문 하나를 단독 묶음으로 처리하거나, 번호가 연속한 주문 두 개를 하나의 묶음으로 처리할 수 있다. 묶음 하나에 주문을 세 개 이상 넣을 수는 없다. 또한 번호가 연속하지 않은 두 주문을 묶거나 주문 순서를 바꿀 수도 없다. 주문 i를 단독 묶음으로 처리하는 비용은 a_i다. 주문 i와 주문 i+1을 두 주문짜리 묶음으로 처리하는 비용은 b_i다. 두 주문짜리 묶음의 비용은 두 단독 비용의 합과 무관하게 별도로 주어진다. 따라서 어떤 두 주문은 함께 처리하는 편이 저렴하고, 다른 두 주문은 각각 처리하는 편이 저렴할 수 있다. 모든 비용은 0 이상의 정수이며, 비용이 0인 묶음도 다른 묶음과 같은 규칙으로 사용할 수 있다. 각 주문은 정확히 하나의 묶음에 포함되어야 한다. 한 주문을 단독으로 처리한 뒤 다른 주문과 다시 묶을 수 없으며, 서로 다른 두 묶음이 같은 주문을 공유해서도 안 된다. 예를 들어 2번과 3번 주문을 함께 처리했다면 1번과 2번 주문을 함께 처리하는 묶음은 사용할 수 없다. 반면 1번과 2번, 3번과 4번을 각각 묶는 것은 가능하다. 선택한 묶음들의 비용을 모두 더한 값이 전체 정산 비용이 된다. 앱은 모든 주문을 빠짐없이 처리하면서 전체 정산 비용을 최소화하려고 한다. 가장 저렴한 묶음 구성이 여러 개라면 어느 구성을 사용해도 되며, 구성 자체는 출력하지 않는다. 주문이 하나뿐이면 두 주문짜리 묶음을 만들 수 없으므로 그 주문을 단독으로 처리해야 한다. 주어진 단독 비용과 인접한 두 주문의 묶음 비용으로 가능한 전체 정산 비용의 최솟값을 구한다.

입력

첫째 줄에 주문 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
둘째 줄에 정수 a_1, a_2, …, a_N이 공백으로 주어진다.
N ≥ 2이면 셋째 줄에 정수 b_1, b_2, …, b_(N-1)이 공백으로 주어진다. N = 1이면 셋째 줄은 주어지지 않는다.
모든 비용은 0 이상 999 이하의 정수다.

출력

모든 주문을 처리하는 전체 정산 비용의 최솟값을 정수 하나로 출력한다.

4
6 7 4 8
5 3 6

11

3
5 1 5
4 2

7

1
0

0

출처: Devin.KR 자체 제작