원정 계획

국제 파이프 및 케이블 회사(International Company of Pipes and Cables)는 태평양을 가로지르는 인터넷 케이블을 운영한다. 그런데 케이블이 작동을 멈췄다. 하지만 당황할 필요는 없다. 상어의 공격으로 이런 일이 가끔 생기기 때문이다. 케이블은 $N + 1$개의 구간이 차례로 이어진 구조이며, 연속한 두 구간 사이마다 중계기가 하나씩 있다. 중계기에는 케이블 위의 위치에 따라 왼쪽에서 오른쪽으로 1부터 $N$까지 서로 다른 정수 번호가 붙어 있다.

신호는 케이블을 따라 왼쪽에서 오른쪽으로 전송된다. 신호가 도달하지 않는 중계기를 오프라인이라고 한다. 이는 중계기보다 앞쪽에 고장 구간이 있다는 뜻이다. 반대로 데이터를 받는 중계기는 온라인이라고 한다. 이는 중계기보다 뒤쪽에 고장 구간이 있다는 뜻이다. 기술진은 고장 구간이 하나뿐이라고 판단했다. 이를 찾아 고치려면 원정이 필요하다.

원정 계획은 진행 중에 얻는 진단 결과에 따라 이동 순서를 정하는 방식이다. 위 그림은 중계기가 $N = 3$개일 때(구간은 $N + 1 = 4$개) 가능한 한 가지 상황을 보여 준다. 이 경우 가능한 원정 계획은 다음 다섯 가지다.

1. 중계기 2를 진단한다. 오프라인이면 중계기 1을 진단해 처음 두 구간 중 어느 쪽이 고장인지 정한다. 반대로 중계기 2가 온라인이면 중계기 3을 진단해 마지막 두 구간 중 어느 쪽이 고장인지 정한다.
2. 중계기 1, 2, 3 순서로 진단하고, 고장 구간을 찾으면 바로 멈춘다.
3. 중계기 1, 3, 2 순서로 진단하고, 고장 구간을 찾으면 바로 멈춘다.
4. 중계기 3, 1, 2 순서로 진단하고, 고장 구간을 찾으면 바로 멈춘다.
5. 중계기 3, 2, 1 순서로 진단하고, 고장 구간을 찾으면 바로 멈춘다.

원정의 총비용은 항해 비용, 잠수 비용, 수리 비용으로 이루어진다. 항해 비용은 항해한 거리에 비례한다. 잠수 비용은 잠수할 때마다 중계기의 깊이에 비례한다. 고장 구간의 수리 비용은 그 구간이 놓인 지형에 따라 정해진다. 위 예시에서 처음 언급한 원정 계획의 비용은 다음과 같다.

• 첫 번째 구간이 고장이면, 원정대는 중계기 2까지 항해해 잠수하고, 중계기 1까지 되돌아가 잠수한 뒤 구간을 수리한다. 항해 비용은 $1 + 1 = 2$, 잠수 비용은 $8 + 3 = 11$, 수리 비용은 $7$이므로 총 $2 + 11 + 7 = 20$이다.
• 두 번째 구간이 고장이면 총비용은 $(1 + 1) + (8 + 3) + (1) = 14$이다.
• 세 번째 구간이 고장이면 총비용은 $(1 + 1) + (8 + 2) + (2) = 14$이다.
• 네 번째 구간이 고장이면 총비용은 $(1 + 1) + (8 + 2) + (12) = 24$이다.

네트워크 장애는 Murphy의 법칙과 유난히 잘 맞아떨어지므로, 원정 계획의 예상 비용은 도달할 수 있는 최댓값으로 본다. 즉, 고장 구간은 언제나 원정 비용을 최대로 만드는 구간이라고 가정한다. 따라서 첫 번째 원정 계획의 예상 비용은 $24$이다. 과제는 모든 원정 계획 가운데 예상 비용의 최솟값을 구하는 것이다. 위 예시에서 중계기 1, 3, 2 순서로 진단하는 계획의 총비용은 고장 구간에 따라 $10$, $17$, $18$, $19$가 된다. 따라서 이 계획의 예상 비용은 $19$이며, 모든 계획 중 가장 작다.

첫 줄에 중계기의 수 $N$ ($2 \le N \le 3000$)이 주어진다. 둘째 줄에는 $N-1$개의 정수 $S_1, S_2, \ldots, S_{N-1}$ ($0 \le S_i \le 10^9$)이 주어진다. $S_i$는 중계기 $i$와 $i + 1$ 사이의 항해 비용이다. 셋째 줄에는 $N$개의 정수 $D_1, D_2, \ldots, D_N$ ($0 \le D_i \le 10^9$)이 주어진다. $D_i$는 중계기 $i$까지 잠수하는 비용이다. 마지막 줄에는 $N + 1$개의 정수 $F_1, F_2, \ldots, F_{N+1}$ ($0 \le F_i \le 10^9$)이 주어진다. $F_i$는 $i$번째 구간을 수리하는 비용이다.

모든 원정 계획 가운데 예상 비용의 최솟값을 한 줄에 정수로 출력한다.