思路

• 设两种状态：

  • $f_i^{(0)}$：第 $i$ 轮以“攻击”结束的最大总伤害；
  • $f_i^{(1)}$：第 $i$ 轮以“闪避”结束的最大总伤害。

• 转移：

题目内容

笨蛋同学正在一款游戏中打 boss，虽然她拥有无限血量，但她发现闪避后的反击伤害可能比直接攻击更高。

游戏共进行 $n$ 轮操作，每轮可选以下两种操作之一：

• 攻击 boss，造成 $a_i$ 点伤害；
• 闪避 boss 的攻击，本轮不造成伤害，但若下轮选择攻击，则此次攻击造成 $b_i$ 点伤害。

输入描述

第一行输入一个整数 $n(1≤n≤2×10^5)$ ，表示游戏轮数；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$ ，表示每轮直接攻击伤害；

第三行输入 $n$ 个整数 $b_1,b_2,...,b_n(1≤b_i≤10^9)$，表示每轮闪避后下轮可造成的伤害。

输出描述

输出一个正整数，表示在最优操作下可造成的最大总伤害。

样例1

输入

6
1 1 4 5 1 4
1 9 1 9 8 1

输出

23

说明

样例解释：

• $n=6$ ；
• {$a_i$}={$1,1,4,5,1,4$}，{$b_i$}={$1,9,1,9,8,1$}；
• 我们选择如下操作序列以获得最大伤害：
  • 第 $1$ 轮直接攻击，造成 $a_1=1$ 点伤害；
  • 第 $2$ 轮闪避，不造成伤害；
  • 第 $3$ 轮攻击，由于前一轮闪避，造成反击伤害 $b_2=9$ ；
  • 第 $4$ 轮直接攻击，造成 $a_4=5$ 点伤害；
  • 第 $5$ 轮闪避，不造成伤害；
  • 第 $6$ 轮攻击，由于前一轮闪避，造成反击伤害 $b_5=8$ 。
• 因此，总伤害为 $1+9+5+8=23$ 。