解题思路

核心思路：每页只有驻留或不驻留两种选择，相邻两页同时驻留才加上 $w$。没有段数限制，用线性动态规划从左到右决策即可。

实现方法：

• 记 $d_0$ 为当前页不驻留时的最大收益，$d_1$ 为当前页驻留时的最大收益。
• 初始：$d_0=0$，$d_1=g_1$。
• 转移到第 $i$ 页：不驻留时 $d_0'=\max(d_0,d_1)$；驻留时 $d_1'=g_i+\max(d_0,\,d_1+w_{i-1})$。

题目内容

某在线推理服务把会话上下文按页写入加速卡上的 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$。