P17018 [ROI 2026 Day1] 分布式系统

某公司有 $n$ 台服务器，编号为 $1$ 到 $n$。第 $i$ 台服务器上运行着 $a_i$ 个服务。 服务器可能会发生故障，因此为每台服务器指定了一台备用服务器。编号为 $i$ 的服务器的备用服务器编号为 $p_i$。若 $p_i = i$，则该服务器为高可靠性服务器，永远不会发生故障。 对于任意两台不同的服务器 $i$ 和 $j$，它们的备用服务器编号 $p_i$ 和 $p_j$ 互不相同。因此，$p$ 是一个长度为 $n$ 的排列，即 $1$ 到 $n$ 的每个数在 $p_1, \ldots, p_n$ 中恰好出现一次。 服务器故障的处理过程如下：若服务器 $i$ 发生故障，则其上运行的全部服务将转移到编号为 $p_i$ 的服务器上，而服务器 $i$ 会被替换为一台全新的服务器，其上不运行任何服务。该服务器的编号及其备用服务器编号保持不变。服务的转移以及服务器的替换过程极快，在此期间不会发生新的故障。 公司计划对系统的运行能力进行一次测试。为此，将令不超过 $k$ 台服务器发生故障。故障是依次发生的，即不会有两台服务器同时故障。请计算：在至多发生 $k$ 次故障后，单台服务器上可能出现的最大服务数量。

第一行包含两个整数 $n$ 和 $k$ ($1 \le k < n \le 10^5$)，分别表示服务器总数以及最多可能发生故障的服务器数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)，表示初始时各服务器上运行的服务数量。 第三行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$)，表示各服务器的备用服务器编号。

输出一个整数，表示答案。

### 说明 考虑第一个样例中能够达到最大答案的故障顺序。 下表展示了各服务器的备用关系： | 服务器 | 1 | 2 | 3 | 4 | |:---:|:---:|:---:|:---:|:---:| | 备用 | 2 | 3 | 4 | 1 | 首先令服务器 2 故障，其上的服务转移到服务器 3，此时服务器 3 上共有 $10 + 7 = 17$ 个服务。 随后令服务器 3 故障，其上的服务转移到服务器 4，此时服务器 4 上共有 $9 + 17 = 26$ 个服务。 为了便于理解，请参考下表，其中记录了上述过程中每台服务器上的服务数量。 | 阶段 | $a_1$ | $a_2$ | $a_3$ | $a_4$ | |:---:|:---:|:---:|:---:|:---:| | 第一次故障前 | 6 | 10 | 7 | 9 | | 服务器 2 故障后 | 6 | 0 | 17 | 9 | | 服务器 3 故障后 | 6 | 0 | 0 | 26 | 如果首先令服务器 3 故障，再令服务器 2 故障，过程将如下所示： | 阶段 | $a_1$ | $a_2$ | $a_3$ | $a_4$ | |:---:|:---:|:---:|:---:|:---:| | 第一次故障前 | 6 | 10 | 7 | 9 | | 服务器 3 故障后 | 6 | 10 | 0 | 16 | | 服务器 2 故障后 | 6 | 0 | 10 | 16 | 此时单台服务器上的最大服务数量为 16，并非最优答案。 在第二个样例中，一种可能的方案是任何服务器都不发生故障。此时服务器 1 上拥有 $1\,000\,000\,000$ 个服务，即为答案。若令服务器 2 或服务器 3 故障，最大服务数量仍出现在服务器 1 上。 ### 子任务 | 子任务 | 分数 | $n$ | 额外限制 | 依赖子任务 | |:---:|:---:|:---:|:---:|:---:| | 1 | 15 | $n \le 1000$ | $k = 1$ | -- | | 2 | 27 | $n \le 1000$ | -- | 1 | | 3 | 21 | -- | $p_i = i \bmod n + 1$ | -- | | 4 | 37 | -- | -- | 1, 2, 3 | 翻译由 DeepSeek V4 Pro 完成