题目内容

共有 $n$ 个时刻，编号 $1$ 到 $n$。给定三个长度为 $n$ 的整数数组 $e,a,b$。

按时刻 $i=1,2,\ldots,n$ 依次发生：

1. 入库：加入 $a_i$ 件物品，每件的过期时刻为 $e_i-1$。一件物品在时刻 $t$ 仍然有效，当且仅当 $t\le e_i-1$。
2. 出库：需要取出 $b_i$ 件当前仍有效的物品（过期时刻 $\ge i$）。若有效库存不足 $b_i$，则能取多少取多少，不足的件数计入缺货。

你可以任意选择取出哪些有效物品。请合理安排每次出库，使所有时刻缺货件数之和最小，输出该最小值。

输入描述

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

第二行 $n$ 个整数 $e_1,e_2,\ldots,e_n$。

第三行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第四行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出描述

输出一个整数，表示最小缺货总件数。

样例1

输入

3
3 4 3
2 1 1
1 3 1

输出

2

说明

时刻 $1$：入库 $2$ 件（过期时刻 $2$），取出 $1$ 件，剩 $1$ 件。

时刻 $2$：入库 $1$ 件（过期时刻 $3$），有效库存共 $2$ 件，需求 $3$，缺货 $1$。无论先用哪一批，总缺货不变。

时刻 $3$：新入库过期时刻为 $2$，已失效；若时刻 $2$ 已用尽库存，则此刻再缺 $1$。

总缺货 $2$。

数据范围

• $1\le n\le 10^5$
• $1\le e_i\le n+1$
• $0\le a_i,b_i\le 10^9$
• 所有输入均为整数