310656: CF1866G. Grouped Carriages

G. Grouped Carriagestime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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$?

Input

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.

Output

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

ExampleInput

7
7 4 2 0 5 8 3
4 0 0 1 3 1 3

Output

5

Note

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]$.

题目大意：
Pak Chanek 观察到火车的车厢在早晨和下午的发车时间总是满的。因此，需要平衡车厢，以避免只有少数几个车厢过于拥挤。
火车包含 N 个从左到右编号为 1 到 N 的车厢。车厢 i 最初包含 A_i 个乘客。所有车厢通过车厢门连接，即对于每个 i (1≤i≤N-1)，车厢 i 和车厢 i+1 通过一个双向门连接。
每个乘客可以在车厢之间移动，但火车规定规定，对于每个 i，从车厢 i 开始的乘客不能通过超过 D_i 个门。
定义 Z 为移动后同一车厢乘客的最大数量。Pak Chanek 问，Z 的最小可能值是多少？

输入输出数据格式：
输入：
第一行包含一个整数 N (1 ≤ N ≤ 2×10^5) — 车厢的数量。
第二行包含 N 个整数 A_1, A_2, A_3, …, A_N (0 ≤ A_i ≤ 10^9) — 每个车厢的初始乘客数量。
第三行包含 N 个整数 D_1, D_2, D_3, …, D_N (0 ≤ D_i ≤ N-1) — 每个起始车厢的门的最大限制数量。

输出：
一个整数，表示 Z 的最小可能值。

示例：
输入：
```
7
7 4 2 0 5 8 3
4 0 0 1 3 1 3
```
输出：
```
5
```

注意：
一种最优策略是：
- 车厢 1 的 5 人移动到车厢 4（通过 3 个门）。
- 车厢 5 的 3 人移动到车厢 3（通过 2 个门）。
- 车厢 6 的 2 人移动到车厢 5（通过 1 个门）。
- 车厢 6 的 1 人移动到车厢 7（通过 1 个门）。
每个车厢的乘客数量变为 [2,4,5,5,4,5,4]。题目大意： Pak Chanek 观察到火车的车厢在早晨和下午的发车时间总是满的。因此，需要平衡车厢，以避免只有少数几个车厢过于拥挤。 火车包含 N 个从左到右编号为 1 到 N 的车厢。车厢 i 最初包含 A_i 个乘客。所有车厢通过车厢门连接，即对于每个 i (1≤i≤N-1)，车厢 i 和车厢 i+1 通过一个双向门连接。 每个乘客可以在车厢之间移动，但火车规定规定，对于每个 i，从车厢 i 开始的乘客不能通过超过 D_i 个门。 定义 Z 为移动后同一车厢乘客的最大数量。Pak Chanek 问，Z 的最小可能值是多少？ 输入输出数据格式： 输入： 第一行包含一个整数 N (1 ≤ N ≤ 2×10^5) — 车厢的数量。 第二行包含 N 个整数 A_1, A_2, A_3, …, A_N (0 ≤ A_i ≤ 10^9) — 每个车厢的初始乘客数量。 第三行包含 N 个整数 D_1, D_2, D_3, …, D_N (0 ≤ D_i ≤ N-1) — 每个起始车厢的门的最大限制数量。 输出： 一个整数，表示 Z 的最小可能值。 示例： 输入： ``` 7 7 4 2 0 5 8 3 4 0 0 1 3 1 3 ``` 输出： ``` 5 ``` 注意： 一种最优策略是： - 车厢 1 的 5 人移动到车厢 4（通过 3 个门）。 - 车厢 5 的 3 人移动到车厢 3（通过 2 个门）。 - 车厢 6 的 2 人移动到车厢 5（通过 1 个门）。 - 车厢 6 的 1 人移动到车厢 7（通过 1 个门）。 每个车厢的乘客数量变为 [2,4,5,5,4,5,4]。