농장 마을

시간 제한2초메모리 제한512 MB

요약

길을 따라 놓인 각 집이 곡물 한 단위를 필요로 하고 두 단위까지 재배할 수 있을 때, 재배 비용과 집 사이 운반 비용의 합을 최소로 만든다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

길을 따라 마을이 하나 있다. 이 마을에는 길을 따라 순서대로 1번부터 $N$ 번까지 번호가 붙은 집 $N$ 채가 있다. 각 집에는 밭이 있어 작물을 최대 두 단위까지 재배할 수 있고, 각 집은 작물 한 단위만 필요로 한다. 모든 집에 작물을 한 단위씩 나누어 주는 데 드는 총비용은 운반 비용과 재배 비용의 합이다.

운반 비용: $i$ 번 집과 $(i+1)$ 번 집 사이에서 작물 한 단위를 옮기는 비용은 $d_i$ 이다. 어느 방향으로 옮기든 비용은 같다.
재배 비용: $i$ 번 집의 밭에서 작물 한 단위를 재배하는 비용은 $g_i$ 이다.

모든 집에 작물을 한 단위씩 공급하는 최소 총비용을 구하시오.

입력

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

N
d1 d2 ... dN-1
g1 g2 ... gN

첫째 줄에 집의 수 $N$ ( $2 \le N \le 200{,}000$ )이 주어진다. 둘째 줄에 공백으로 구분된 정수 $N-1$ 개가 주어진다. $i$ 번째 정수 $d_i$ ( $1 \le d_i \le 10^9$ , $1 \le i \le N-1$ )는 $i$ 번 집과 $(i+1)$ 번 집 사이의 운반 비용이다. 셋째 줄에 공백으로 구분된 정수 $N$ 개가 주어진다. $i$ 번째 정수 $g_i$ ( $1 \le g_i \le 10^9$ , $1 \le i \le N$ )는 $i$ 번 집 밭의 재배 비용이다.

출력

모든 집에 작물을 한 단위씩 공급하는 최소 비용을 출력한다.

예제3

예제 1
입력
```
2
3
1 5
```
예상 출력
```
5
```
예제 2
입력
```
3
100 100
1 2 3
```
예상 출력
```
6
```
예제 3
입력
```
4
1 2 3
1 1 100 100
```
예상 출력
```
12
```