CF1866G.Grouped Carriages

Pak Chanek observes that the carriages of a train is always full on morning departure hours and afternoon departure hours. Therefore, the balance between carriages is needed so that it is not too crowded in only a few carriages.

A train contains $N$ carriages that are numbered from $1$ to $N$ from left to right. Carriage $i$ initially contains $A_i$ passengers. All carriages are connected by carriage doors, namely for each $i$ ($1\leq i\leq N-1$), carriage $i$ and carriage $i+1$ are connected by a two-way door.

Each passenger can move between carriages, but train regulation regulates that for each $i$, a passenger that starts from carriage $i$ cannot go through more than $D_i$ doors.

Define $Z$ as the most number of passengers in one same carriage after moving. Pak Chanek asks, what is the minimum possible value of $Z$?

帕克·查内克观察到，列车车厢在早晨出发时段和下午出发时段总是满员的。因此，需要对车厢之间的乘客数量进行平衡，以避免仅有少数几个车厢过度拥挤。

一列火车包含 $N$ 节车厢，从左至右依次编号为 $1$ 到 $N$。初始时，第 $i$ 节车厢有 $A_i$ 名乘客。所有车厢之间均通过车厢门相互连通；具体来说，对每个 $i$（$1\leq i\leq N-1$），第 $i$ 节车厢与第 $i+1$ 节车厢之间有一扇双向通行的门。

每名乘客可在车厢间移动，但列车规定：对每个 $i$，一名起始于第 $i$ 节车厢的乘客最多只能穿过 $D_i$ 扇门。

定义 $Z$ 为移动结束后，单节车厢中乘客数量的最大值。帕克·查内克提出问题：$Z$ 的最小可能值是多少？

The first line contains a single integer $N$ ($1 \leq N \leq 2\cdot10^5$) — the number of carriages.

The second line contains $N$ integers $A_1, A_2, A_3, \ldots, A_N$ ($0 \leq A_i \leq 10^9$) — the initial number of passengers in each carriage.

The third line contains $N$ integers $D_1, D_2, D_3, \ldots, D_N$ ($0 \leq D_i \leq N-1$) — the maximum limit of the number of doors for each starting carriage.

第一行包含一个整数 $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$）——每节起始车厢最多允许的车门数量。

An integer representing the minimum possible value of $Z$.

表示 $Z$ 的最小可能值的整数。

One strategy that is optimal is as follows:

• $5$ people in carriage $1$ move to carriage $4$ (going through $3$ doors).
• $3$ people in carriage $5$ move to carriage $3$ (going through $2$ doors).
• $2$ people in carriage $6$ move to carriage $5$ (going through $1$ door).
• $1$ person in carriage $6$ moves to carriage $7$ (going through $1$ door).

The number of passengers in each carriage becomes $[2,4,5,5,4,5,4]$.

一种最优策略如下：

• 车厢 $1$ 中的 $5$ 人移动到车厢 $4$（经过 $3$ 扇门）。
• 车厢 $5$ 中的 $3$ 人移动到车厢 $3$（经过 $2$ 扇门）。
• 车厢 $6$ 中的 $2$ 人移动到车厢 $5$（经过 $1$ 扇门）。
• 车厢 $6$ 中的 $1$ 人移动到车厢 $7$（经过 $1$ 扇门）。

各车厢中的乘客数变为 $[2,4,5,5,4,5,4]$。