Problem Description

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.

Input Format

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 Format

Output one integer, representing the answer.

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

Hint

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:

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.

If we first let server 3 fail, and then let server 2 fail, the process is as follows:

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

Translated by DeepSeek V4 Pro.

Translated by ChatGPT 5