Maximizing Contest Reward

Xiao Dou is taking part in an intelligence competition along with his n friends (his support team). There are a total of m questions. Each contestant is allowed exactly one turn. In a turn, the contestant selects any question to answer. After answering correctly, he is allowed to continue answering the follow‐up question of the one he just solved. This chain continues until either a mistake is made (which will not happen in this problem) or there is no follow‐up question.

Each question has an associated positive integer value. At the end of the contest, the reward a contestant receives is equal to the minimum value among all the questions that were not answered by him and his support team. Because Xiao Dou and his friends are exceptionally strong, they will answer every question they attempt correctly. However, since each person only gets one turn, they must plan which questions to attempt. In any turn, if a contestant starts answering a chain at some question, then he will automatically answer every question following (via the follow‐up pointers) until the chain ends. Note that by choosing a starting question in the middle of a chain, the problems before that question will remain unanswered.

The goal is to maximize the final reward value by strategically choosing, for some chains, to answer from the first occurrence of a question that would lower the overall reward if left unanswered. In other words, for each chain of questions, if there is a question with value less than a threshold \(X\), one may use a turn to cover (i.e. answer) that question and all subsequent questions, so that the remaining (unanswered) questions in that chain are all at least \(X\). However, at least one entire chain must be left completely unanswered (so that there is at least one leftover question from which the reward is computed). Given the contest rules and the structure of follow‐up questions, determine the maximum reward value \(R\) that Xiao Dou can obtain.

Note: The follow‐up relationship is given for each question. For the i-th question, if the follow-up question index is 0 then there is no follow–up question. Otherwise, it points to the next question in that chain.

The answer must be computed using an optimal strategy. A suggested approach is to use binary search over possible reward thresholds \(X\) and, for each chain (which is formed by following the follow–up pointers starting from a question with no predecessor), decide if it needs to be covered (i.e. answered starting from the first question with value below \(X\)) in order to avoid lowering the overall reward. With a team of \(n+1\) people, at most \(n\) chains may be covered (since at least one chain must be left uncovered to provide the reward value).

The final answer is the maximum integer \(X\) for which the number of chains that require covering does not exceed \(n\) and at least one chain is left uncovered.

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(m\), where \(n\) is the number of friends (note that Xiao Dou is also part of the team, so there are \(n+1\) contestants) and \(m\) is the number of questions.
2. The second line contains \(m\) positive integers. The i-th integer represents the value of the i-th question.
3. The third line contains \(m\) integers. The i-th integer indicates the follow–up question for the i-th question. A value of 0 means there is no follow–up question.

You may assume that the questions form one or more chains (i.e. each chain starts with a question that has no predecessor and continues via follow–up pointers). If some questions are not reached from any head, treat each unvisited question as a separate chain.

outputFormat

Output a single integer: the maximum reward value that Xiao Dou and his support team can obtain.

sample

1 5
5 3 7 10 9
2 3 0 5 0

9