AT_kupc2015_d 高橋君の旅行

高桥君正在游览一个名叫时尚城市的地方。这个城市由 $N+1$ 个连续的城镇组成，依次命名为城镇 $1$、城镇 $2$、……、城镇 $N+1$。 他计划在这里进行 $N$ 天的旅行。旅行开始时，他身上有 $0$ 元钱，并且位于城镇 $1$。在第 $i$ 天（$i = 1, \ldots, N$），高桥君有两种选择： - 从当前所在的城镇 $k$ 移动到城镇 $k+1$，此时他的余额将变化 $A_k$。 - 继续停留在当前的城镇 $k$，此时他的余额将变化 $B_k$。 高桥君要制定一个使得旅行计划满足以下要求： - 每一天结束时，他都不能出现负债。 - 在整个旅程的最后一天，也就是第 $N$ 天结束时，他的钱数达到最大。 请计算并输出在这个旅行计划下，他在第 $N$ 天结束时能够拥有的最大金额。

输入通过标准输入给出，格式如下： > $N$ > $A_1$ $A_2$ ... $A_N$ > $B_1$ $B_2$ ... $B_N$ - 第一行是一个整数 $N$（$2 \leq N \leq 10^5$），表示旅行的天数。 - 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，每个整数 $A_i$ 表示从城镇 $i$ 移动到城镇 $i+1$ 时的余额变化，范围为 $-10^9$ 到 $10^9$。 - 第三行也包含 $N$ 个整数 $B_1, B_2, \ldots, B_N$，每个整数 $B_i$ 表示在城镇 $i$ 停留时的余额变化，范围为 $0$ 到 $10^9$。

输出高桥君在第 $N$ 天结束时可能拥有的最大金额。

### 部分分 如果程序能正确处理以下特殊情况的数据集，将获得 $3$ 分的部分分： - $N \leq 100$。 **本翻译由 AI 自动生成**