题目描述

题目译自 XXXII Olimpiada Informatyczna – II etap Schody

在 Bajtocorp 公司所在的 $n$ 层摩天大楼里，预算拮据导致没有电梯，员工只能靠楼梯在楼层间穿梭。受安全规范约束，每单位时间内，连接第 $i$ 层与第 $i+1$ 层的楼梯最多允许一名员工通过，无论是上行（从 $i$ 层到 $i+1$ 层）还是下行（从 $i+1$ 层到 $i$ 层）。更严格的是，同一楼梯不可同时处理上行和下行，但不同楼层间的楼梯可同时使用。

Bajtazar 作为公司总裁，仔细统计了当前情况：第 $i$ 层有 $a_i$ 名员工。他希望重新分配员工，使第 $i$ 层达到 $b_i$ 名员工的目标人数，而具体员工的去向并不重要，只要每层人数符合预期即可。你的任务是帮助他计算，从当前分布调整到目标分布所需的最少单位时间。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^6)$，表示大楼层数。

第二行包含 $n$ 个整数 $a_i$ $(0 \leq a_i \leq 10^9)$，表示初始时第 $i$ 层的员工数。

第三行包含 $n$ 个整数 $b_i$ $(0 \leq b_i \leq 10^9)$，表示目标时第 $i$ 层的员工数。

保证 $\sum a_i = \sum b_i$。

输出格式

输出一个整数，表示从初始状态到目标状态所需的最少单位时间。

3
1 0 1
0 2 0

1

附加样例

1. $n=1000$，若 $i \bmod 10 = 0$，则 $a_i = b_{n+1-i} = i / 10$，否则 $a_i = b_{n+1-i} = 0$，答案为 $2558$。
2. $n=1000$，$a_i = b_{n+1-i} = 10 \cdot i$，答案为 $2500000$。
3. $n=1000000$，$a_i = i \bmod 2, b_i = 1 - a_i$，答案为 $1$。
4. $n=1000000$，若 $i \leq 500000$，则 $a_i = 10^6, b_i = 0$，否则 $a_i = 0, b_i = 10^6$，答案为 $5 \cdot 10^{11}$。

数据范围与提示

详细子任务附加限制及分值如下表所示。