P17018 [ROI 2026 Day1] Distributed System

A company has $n$ servers, numbered from $1$ to $n$. Server $i$ is running $a_i$ services. Servers may fail, so each server is assigned a backup server. The backup server of server $i$ is $p_i$. If $p_i = i$, then this server is a high-reliability server and will never fail. For any two different servers $i$ and $j$, their backup server numbers $p_i$ and $p_j$ are different. Therefore, $p$ is a permutation of length $n$, meaning each number from $1$ to $n$ appears exactly once among $p_1, \ldots, p_n$. Failures are handled as follows: if server $i$ fails, all services running on it are transferred to server $p_i$, and server $i$ is replaced by a brand-new server that runs no services. The server number and its backup server number remain unchanged. The service transfer and server replacement happen very quickly, and no new failure will occur during this period. The company plans to test the system's capacity. For this, at most $k$ servers will be made to fail. Failures happen one by one, i.e., no two servers fail at the same time. Compute the maximum possible number of services that can appear on a single server after at most $k$ failures.

The first line contains two integers $n$ and $k$ ($1 \le k < n \le 10^5$), representing the total number of servers and the maximum number of servers that may fail. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), representing the initial number of services running on each server. The third line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$), representing the backup server number of each server.

Output one integer, representing the answer.

### Explanation Consider a failure order that can achieve the maximum answer in the first sample. The table below shows the backup relationships of the servers: | Server | 1 | 2 | 3 | 4 | |:---:|:---:|:---:|:---:|:---:| | Backup | 2 | 3 | 4 | 1 | First, let server 2 fail. Its services are transferred to server 3, so server 3 now has $10 + 7 = 17$ services. Next, let server 3 fail. Its services are transferred to server 4, so server 4 now has $9 + 17 = 26$ services. For easier understanding, refer to the table below, which records the number of services on each server during the process above. | Stage | $a_1$ | $a_2$ | $a_3$ | $a_4$ | |:---:|:---:|:---:|:---:|:---:| | Before the first failure | 6 | 10 | 7 | 9 | | After server 2 fails | 6 | 0 | 17 | 9 | | After server 3 fails | 6 | 0 | 0 | 26 | If we first let server 3 fail, and then let server 2 fail, the process is as follows: | Stage | $a_1$ | $a_2$ | $a_3$ | $a_4$ | |:---:|:---:|:---:|:---:|:---:| | Before the first failure | 6 | 10 | 7 | 9 | | After server 3 fails | 6 | 10 | 0 | 16 | | After server 2 fails | 6 | 0 | 10 | 16 | At this time, the maximum number of services on a single server is 16, which is not the optimal answer. In the second sample, one possible plan is that no server fails. Then server 1 has $1\,000\,000\,000$ services, which is the answer. If server 2 or server 3 fails, the maximum number of services still appears on server 1. ### Subtasks | Subtask | Score | $n$ | Additional Constraints | Dependencies | |:---:|:---:|:---:|:---:|:---:| | 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 | Translated by DeepSeek V4 Pro. Translated by ChatGPT 5