题目描述

某公司有 $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$)，表示各服务器的备用服务器编号。

输出格式

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

4 2
6 10 7 9
2 3 4 1

26

3 1
1000000000 993 2010
1 3 2

1000000000

11 5
3 5 12 7 5 9 2 6 0 9 4
2 8 9 6 5 11 3 1 10 7 4

23

提示

说明

考虑第一个样例中能够达到最大答案的故障顺序。

下表展示了各服务器的备用关系：

首先令服务器 2 故障，其上的服务转移到服务器 3，此时服务器 3 上共有 $10 + 7 = 17$ 个服务。

随后令服务器 3 故障，其上的服务转移到服务器 4，此时服务器 4 上共有 $9 + 17 = 26$ 个服务。

为了便于理解，请参考下表，其中记录了上述过程中每台服务器上的服务数量。

如果首先令服务器 3 故障，再令服务器 2 故障，过程将如下所示：

此时单台服务器上的最大服务数量为 16，并非最优答案。

在第二个样例中，一种可能的方案是任何服务器都不发生故障。此时服务器 1 上拥有 $1\,000\,000\,000$ 个服务，即为答案。若令服务器 2 或服务器 3 故障，最大服务数量仍出现在服务器 1 上。

子任务

翻译由 DeepSeek V4 Pro 完成