78계단 내려가기 대회

먼 훗날, 포스텍 캠퍼스에서는 늘어만 가는 신입생을 모두 수용하기 위해 증축 공사가 계속되었다. 그 결과 많은 시설이 예전과는 비교할 수 없을 만큼 큰 규모로 바뀌었다. 특히 78계단은 여러 차례 공사를 거쳐 $N$개의 칸으로 이루어진 거대한 계단이 되었다. 각 칸은 1번부터 $N$번까지 번호로 구분되며, $i$번 칸의 높이는 $H_i$이다. 계단이므로 각 칸의 높이는 번호에 대해 단조감소한다.

미래의 포스텍 재학생들은 이 78계단을 가장 잘 활용하는 방법을 찾았고, 그것이 78계단 내려가기 대회이다. 참가자는 1번 칸에서 출발해 번호가 더 큰 칸으로 계속 내려가서 $N$번 칸에 도착해야 한다. 여러 칸을 뛰어넘을 수 있으며, 번호가 더 작은 칸으로는 이동할 수 없다. 1번 칸을 제외한 모든 칸에는 보물 상자가 1개씩 놓여 있다. $i$번 칸의 보물 상자는 점수 $A_i$와 내구도 $B_i$를 가진다. $i$번 칸의 보물 상자를 열어 점수를 얻으려면 직전에 있던 칸의 높이가 $H_i+B_i$ 이상이어야 한다.

목표는 가장 많은 점수를 얻어 대회에서 우승하는 것이다. 각 칸에 놓인 보물 상자의 점수와 내구도가 주어질 때, 얻을 수 있는 점수의 최댓값을 구하라.

첫 번째 줄에 계단을 이루는 칸의 수 $N$이 주어진다. ($2 \le N \le 300,000$)

두 번째 줄에 각 칸의 높이를 나타내는 $N$개의 정수 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 주어진다. ($0 \le H_i \le 10^9$; $H_i \ge H_{i+1}$)

세 번째 줄에 각 칸에 놓인 보물 상자의 점수를 나타내는 $N-1$개의 정수 $A_2, A_3, \cdots, A_N$이 공백으로 구분되어 주어진다. ($0 \le A_i \le 10^9$)

네 번째 줄에 각 칸에 놓인 보물 상자의 내구도를 나타내는 $N-1$개의 정수 $B_2, B_3, \cdots, B_N$이 공백으로 구분되어 주어진다. ($0 \le B_i \le 10^9$)

얻을 수 있는 점수의 최댓값을 출력한다.