25492번 - 전깃줄 연결

신촌 왕국은 현재 재개발 공사가 한창이다. 일렬로 된 도로에 $N$개의 전봇대가 설치되어 있는데, 이 중 일부를 제거하고 사이를 전깃줄로 연결하는 작업이다. 전봇대를 순서대로 $1$번부터 $N$번이라고 했을 때, $1$번 전봇대 아래에 있는 발전소로부터 $N$번 전봇대 아래에 있는 마을에 전력을 공급해야 한다. 두 전봇대 사이에 전깃줄이 없으면 전기가 흐르지 않는다.

어떤 $i$번 전봇대와 $j$번 전봇대$(1 \le i < j \le N)$ 사이에 전깃줄을 설치하는 비용은 다음과 같다.

$$ C_i - 2 \cdot \gcd(C_i, C_{i+1}, \dots, C_j) + C_j $$

단, 전깃줄을 설치하려면 먼저 그 사이에 있는 전봇대를 모두 제거해야 한다. 이때 $i$번째 전봇대를 제거하는 비용은 $B_i$이다. 당연하게도 $1$번 전봇대에서 $N$번 전봇대까지 연결하는 비용을 최소로 만들고 싶다. 신촌 왕국을 도와 최소 비용으로 전깃줄 작업을 진행해보자!

첫 번째 줄에 $N$이 주어진다. $(2 \le N \le 200\,000)$

두 번째 줄에 정수 $C_1, C_2, \dots, C_N$이 공백으로 구분되어 주어진다. $(1 \le C_i \le 10^9)$

세 번째 줄에 정수 $B_1, B_2, \dots, B_N$이 공백으로 구분되어 주어진다. $(1 \le B_i \le 10^9)$

$1$번 전봇대에서 $N$번 전봇대까지 연결하는 최소 비용을 출력한다.