Một phân hoạch của $[0, N)$ là một dãy số nguyên $S = (s_0, \dots, s_r)$ thỏa mãn ba điều kiện sau:

• $s_0 = 0$,
• $s_r = N$,
• $s_i < s_{i+1}$ ($0 \le i < r$).

Nói cách khác, với mỗi $i$, $[s_i, s_{i+1})$ biểu diễn một khoảng liên tục, và $[0, N)$ là hợp của $r$ khoảng này.

Cho ba dãy số có độ dài $N$ gồm các số nguyên nằm trong khoảng từ $-10^9$ đến $10^9$: $A$ $(a_0, \dots, a_{N-1})$, $B$ $(b_0, \dots, b_{N-1})$, $C$ $(c_0, \dots, c_{N-1})$.

Gọi điểm số của phân hoạch $S$ là $f(S)$ được định nghĩa như sau:

$$f(S) = \min_{0 \le i < r} \left\{ b_{s_i} + c_{s_{i+1}-1} + \sum_{s_i \le j < s_{i+1}} a_j \right\}$$

Hãy tìm giá trị lớn nhất của $f$ trên tất cả các phân hoạch $S$ có thể.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$ ($1 \le N \le 2 \cdot 10^5$). Dòng thứ hai chứa $N$ số nguyên: số thứ $i$ biểu thị $a_i$. Dòng thứ ba và thứ tư mô tả các dãy $b$ và $c$ theo cùng định dạng ($-10^9 \le a_i, b_i, c_i \le 10^9$).

Dữ liệu ra

In ra một số nguyên duy nhất: điểm số lớn nhất trên tất cả các phân hoạch có thể.

Ví dụ

Dữ liệu vào 1

2
1 -1
-1 4
1 -2

Dữ liệu ra 1

1

Dữ liệu vào 2

1
1000000000
1000000000
1000000000

Dữ liệu ra 2

3000000000