题目内容

某在线推理服务把会话上下文按页写入加速卡上的 KV 缓存。一页对应一段连续 Token。调度器要决定每一页是否留在卡上（驻留）；不驻留的页在下次命中时从主机内存回填。

共有 $n$ 页，按对话顺序编号为 $1$ 到 $n$。

• 若驻留第 $i$ 页，得到净收益 $g_i$，可为负。
• 若第 $i$ 页与第 $i+1$ 页同时驻留，额外得到收益 $w_i$（$w_i \ge 0$）。只有相邻且都驻留时才计入。
• 各页相互独立地选择驻留或不驻留，没有段数上限。
• 允许一页都不驻留，此时收益为 $0$。

求净收益的最大值。

输入描述

第一行一个整数 $n$，表示页数。

第二行 $n$ 个整数 $g_1, g_2, \ldots, g_n$，表示各页单独驻留的净收益。

第三行 $n-1$ 个整数 $w_1, w_2, \ldots, w_{n-1}$，其中 $w_i$ 为第 $i$ 页与第 $i+1$ 页同时驻留时的额外收益。

约束

$2 \le n \le 10^{5}$

$-10^{4} \le g_i \le 10^{4}$

$0 \le w_i \le 10^{4}$

输出描述

输出一行一个整数，表示最大净收益。

样例1

输入

5
4 -3 5 -10 6
2 2 1 3

输出

16

说明

驻留第 $1,2,3$ 页：单页收益 $4+(-3)+5=6$，邻页共用 $2+2=4$，小计 $10$。第 $4$ 页不驻留。第 $5$ 页驻留，再得 $6$。合计 $16$。

若四页与第 $5$ 页一起全留，单页 $4+(-3)+5+(-10)+6=2$，邻页共用 $2+2+1+3=8$，合计 $10$，更差。

样例2

输入

3
10 -100 10
1 1

输出

20

说明

第 $2$ 页亏损很大，留下只为了吃两侧 $w$ 也不划算：$10+(-100)+10+1+1=-78$。不驻留第 $2$ 页、只留两端，收益 $10+10=20$。