Pak Chanek 观察到,火车的车厢在早上出发时间和下午出发时间总是满员。因此,车厢之间需要保持平衡,这样只有几节车厢才不会太拥挤。
一列火车包含 $$$N$$$ 车厢,从左到右编号为 $$$1$$$ 到 $$$N$$$。 $$$i$$$ 车厢最初载有 $$$A_i$$$ 乘客。所有车厢均由车厢门连接,即对于每个 $$$i$$$ ($$$1\leq i\leq N-1$$$),车厢 $$$i$$$ 和车厢 $$$i+1$$$ 由双向门连接。
每个乘客都可以在车厢之间移动,但火车法规规定,对于每个 $$$i$$$,从车厢 $$$i$$$ 出发的乘客不能通过超过 $$$D_i$$$ 个门。
将 $$$Z$$$ 定义为移动后同一车厢内的乘客人数最多。 Pak Chanek 问,$$$Z$$$ 的最小可能值是多少?
输入
第一行包含一个整数 $$$N$$$ ($$$1 \leq N \leq 2\cdot10^5$$$) — 车厢数量。
第二行包含 $$$N$$$ 整数 $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$0 \leq A_i \leq 10^9$$$) — 每节车厢的初始乘客数量。
第三行包含 $$$N$$$ 整数 $$$D_1, D_2, D_3, \ldots, D_N$$$ ($$$0 \leq D_i \leq N-1$$$) — 每个起始车厢的门数的最大限制。
输出
一个整数,表示 $$$Z$$$ 的最小可能值。
示例
输入 #1
7 7 4 2 0 5 8 3 4 0 0 1 3 1 3
输出 #1
5
注意
一种最佳策略如下:
- $$$5$$$车厢里的人$$$1$$$移动到车厢$$$4$$$(穿过$$$3$$$门)。
- $$$3$$$车厢里的人$$$5$$$移动到车厢$$$3$$$(穿过$$$2$$$门)。
- $$$2$$$车厢里的人$$$6$$$移动到车厢$$$5$$$(通过$$$1$$$门)。
- 车厢$$$6$$$中的$$$1$$$人移动到$$$7$$$车厢(通过$$$1$$$门)。
每节车厢的乘客人数变为$$$[2,4,5,5,4,5,4]$$$。