시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
2.0 초 512 MB 4701 1997 (42%) 1722
문제
명우네 공장에는 두 개의 생산라인이 있고, 각 라인에는 $n$개의 공정이 순서대로 있다. 하나의 제품이 완성이 되려면 두 생산라인 중 한 생산라인을 정해, 그 생산라인에 미완성 제품이 들어가고 그 생산라인의 $n$개의 공정을 순서대로 지나, 생산라인에서 생산을 마무리하여 완성된다. 중간에 생산라인을 바꿀 수도 있다. 첫 번째 생산라인의 $i$번째 공정에서 소요되는 시간은 $S_{1, i}$이고, 두 번째 생산라인의 $i$번째 공정에서 소요되는 시간은 $S_{2, i}$이다. 그리고 첫 번째 생산라인에 진입하는 시간은 $e_1$, 두 번째 생산라인에 진입하는 시간은 $e_2$이고, 첫 번째 생산라인에서 생산을 마무리 하는 시간은 $x_1$, 두 번째 생산라인에서 생산을 마무리 하는 시간은 $x_2$이다. 마지막으로 첫 번째 생산라인의 $i$번째 공정을 마치고 두 번째 생산라인으로 바꾸는데 걸리는 시간은 $t_{1, i}$이고, 두 번째 생산라인의 $i$번째 공정을 마치고 첫 번째 생산라인으로 바꾸는데 걸리는 시간은 $t_{2, i}$이다. 즉, 명우의 공장은 아래와 같은 그림으로 표현된다. ![생산 라인](/download_file/819d412120e4576553fe9a18d62375f16b5f4549db9abb7f77c724b9de1de682/%EA%B7%B8%EB%A6%BC1.png/?show=true) 명우는 자신이 만들어놓은 공장에서 하나의 제품을 만드는데 걸리는 최소 시간을 알고 싶어한다. 명우를 도와 하나의 제품을 만드는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.
입력
첫 줄에 라인별 공정의 개수 $n$, 라인별 진입 시간과 마무리 시간 $e_1$, $e_2$, $x_1$, $x_2$가 주어진다. ($2 \leq n \leq 300,000$, $1 \leq e_1, e_2, x_1, x_2 \leq 200$) 두 번째 줄에 $S_{1, 1}, S_{1, 2}, \dots, S_{1, n}$를 나타내는 $n$개의 자연수가 공백으로 구분되어 주어진다. ($1 \leq S_{1, i} \leq 200$) 세 번째 줄에 $S_{2, 1}, S_{2, 2}, \dots, S_{2, n}$를 나타내는 $n$개의 자연수가 공백으로 구분되어 주어진다. ($1 \leq S_{2, i} \leq 200$) 네 번째 줄에 $t_{1, 1}, t_{1, 2}, \dots, t_{1, n-1}$를 나타내는 $n-1$개의 자연수가 공백으로 구분되어 주어진다. ($1 \leq t_{1, i} \leq 200$) 다섯 번째 줄에 $t_{2, 1}, t_{2, 2}, \dots, t_{2, n-1}$를 나타내는 $n-1$개의 자연수가 공백으로 구분되어 주어진다. ($1 \leq t_{2, i} \leq 200$)
출력
첫 줄에 하나의 제품을 만드는데 걸리는 최소 시간을 출력한다.
힌트
#### 입력 예제 ``` 6 2 4 3 2 7 9 3 4 8 4 8 5 6 4 5 7 2 1 1 3 4 2 1 2 2 1 ``` #### 출력 예제 ``` 38 ```