P16366 [OOI 2026] Anxiety Before the Olympiad

Before entering a closed olympiad in informatics, there are $n$ participants waiting for entrance, numbered from $1$ to $n$. It is known that every minute, one participant will be invited into the competition hall in the order of their numbers. In one minute, the first participant will enter the hall, in two minutes the second participant will enter, and so on. Thus, the $i$-th participant will enter the hall $i$ minutes after the start of the entrance process. Each participant has a certain level of anxiety before the olympiad. The anxiety level of each participant is given by some integer (which may be negative). Before the start of the entrance process, the anxiety level of participant $i$ is equal to $a_i$. Every minute, the anxiety level of the participant will change by $b_i$. Therefore, after $x$ minutes from the start of the entrance process, the anxiety level of participant $i$ will be equal to $a_i + x \cdot b_i$. Alexander is an experienced psychologist who decided to calm the participants waiting to enter the olympiad. To do this, Alexander talks to the participants and calms them down. He can talk to each participant no more than once. After talking to Alexander, the anxiety level of the participant becomes $0$ and does not change afterward. The $\textit{effectiveness}$ of Alexander's work with participant $i$ is considered to be the level of anxiety of the participant at the moment of communication with Alexander. Thus, if Alexander talks to participant $i$ after $t_i$ minutes from the start of the entrance process into the olympiad, the $\textit{effectiveness}$ will be equal to $a_i + t_i \cdot b_i$. Note that if the anxiety level of the participant was negative, then the $\textit{effectiveness}$ will also be negative. Alexander will work with the participants in the order of their numbers. However, Alexander does not have to talk to all participants, meaning it is possible that he will not communicate with the last participants in line. Note that Alexander will talk to each participant no more than once and this must happen before the participant enters the competition hall. At the same time, Alexander can communicate with several participants at once every minute. More formally, Alexander's work process can be described as follows: - In total, Alexander will talk to the first $k$ participants in line, where $k$ is chosen by him. - For each of the first $k$ participants, we will fix a non-negative integer $t_i$ --- the time of communication with Alexander. Note that $t_i$ can be equal to zero, which means that Alexander talked to participant $i$ before the first participant was allowed into the competition hall. - For each $i$ from $1$ to $k$, $t_i < i$, as Alexander must talk to the participants before they enter the competition hall. - For each $i$ from $1$ to $k - 1$, $t_i \le t_{i + 1}$, as Alexander talks to the participants in the order of their numbers. - The $\textit{total effectiveness}$ of Alexander's communication with the participants will be described by the following formula: $$\sum_{i = 1}^k \left(a_i + t_i \cdot b_i\right)$$ Alexander has a predetermined plan for working with the participants. The work plan is given by a sequence of $n$ integers $p_1$, $p_2$, $\ldots$, $p_n$. For each $i$, if $p_i \neq -1$, then by the time the first $i$ participants are allowed into the competition hall (after $i$ minutes from the start of the entrance process), Alexander must talk to the first $p_i$ participants and no one else. In this case, it is also guaranteed that $p_i \ge i$. If $p_i = -1$, it means that there are no restrictions on the number of participants with whom Alexander must work after $i$ minutes from the start of the entrance process. More formally, if $p_i \neq -1$, then: - $p_i \ge i$; - $t_{p_i} < i$; - For any $j$, such that $p_i < j \le k$, it holds that $t_j \ge i$. Help Alexander determine what the maximum possible $\textit{total effectiveness}$ of his work with the participants can be while satisfying all the constraints. It is guaranteed that the answer always exists.

The first line contains a single integer $n$ ($1 \le n \le 10^6$) --- the number of participants waiting in line to enter the competition hall of the olympiad. The next $n$ lines contain two integers $a_i$ and $b_i$ ($-10^9 \le a_i \le 10^9$, $-10^6 \le b_i \le 10^6$) --- the anxiety parameters of the $i$-th participant. The following line contains $n$ integers $p_1$, $p_2$, $\ldots$, $p_n$ ($i \le p_i \le n$ or $p_i = -1$) --- the description of the work plan for Alexander. It is guaranteed that for any pair $1 \le i < j \le n$, it holds that $p_i \le p_j$, if $p_i \ne -1$ and $p_j \ne -1$.

Output a single number --- the maximum possible $\textit{total effectiveness}$ of Alexander's work. It can be shown that Alexander will always be able to perform his work while adhering to all additional constraints and the work plan.

### Note In the first test example, it is optimal to choose $k=4$ and $t = \{0, 0, 0, 3\}$. Then the $\textit{total effectiveness}$ will be: $$ \left(3 + t_0 \cdot (-6)\right) + \left(4 + t_1 \cdot (-3)\right) + \left(-7 + t_2 \cdot (-3) \right) + \left(-3 + t_4 \cdot 6\right) = $$ $$ = \left(3 + 0 \cdot (-6)\right) + \left(4 + 0 \cdot (-3)\right) + \left(-7 + 0 \cdot (-3) \right) + \left(-3 + 3 \cdot 6\right) = 15 $$ In the second test example, it is optimal to choose $k=3$ and $t = \{0, 0, 1\}$. Then the $\textit{total effectiveness}$ will be: $$ \left(-6 + t_0 \cdot (-1)\right) + \left(-5 + t_1 \cdot 14\right) + \left(0 + t_2 \cdot 10\right) = \left(-6 + 0 \cdot (-1)\right) + \left(-5 + 0 \cdot 14\right) + \left(0 + 1 \cdot 10\right) = -1 $$ In the third test example, it is optimal to choose $k=3$ and $t = \{0, 1, 2\}$. Then the $\textit{total effectiveness}$ will be: $$ \left(-6 + t_0 \cdot (-1)\right) + \left(-5 + t_1 \cdot 14\right) + \left(0 + t_2 \cdot 10\right) = \left(-6 + 0 \cdot (-1)\right) + \left(-5 + 1 \cdot 14\right) + \left(0 + 2 \cdot 10\right) = 23 $$ ### Scoring The tests for this problem consist of fourteen groups. Points for each group are awarded only if all tests of the group and all tests of some previous groups are passed. Note that passing the tests from the statement is not required for some groups. $\textbf{Offline testing}$ means that the results of testing your solution on this group will only be available after the end of the competition. The final score for each group is equal to the maximum score obtained for that group of tests across all submissions. | Group | Points | Additional constraints | < | < | Necessary groups | Comment | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | $n$ | $b_i$ | $p_i$ | | | | $0$ | $0$ | -- | -- | -- | -- | Tests from the statement. | | $1$ | $6$ | $n \le 100$ | -- | $p_i=-1$ | -- | | | $2$ | $6$ | ^ | ^ | -- | $0$ -- $1$ | ^ | | $3$ | $7$ | $n \le 5000$ | -- | $p_i=-1$ | $1$ | | | $4$ | $6$ | ^ | ^ | -- | $0$ -- $3$ | ^ | | $5$ | $7$ | -- | $b_i \le 0$ | $p_i=-1$ | -- | | | $6$ | $5$ | ^ | ^ | -- | $5$ | ^ | | $7$ | $7$ | -- | $b_i \ge 0$ | $p_i=-1$ | -- | | | $8$ | $5$ | ^ | ^ | -- | $7$ | ^ | | $9$ | $9$ | -- | $b_i \le b_{i+1}$ | $p_i=-1$ | -- | | | $10$ | $8$ | ^ | ^ | -- | $9$ | ^ | | $11$ | $10$ | $n \le 100\,000$ | -- | $p_i=-1$ | -- | Number $b_i > 0$ no more than 10 | | $12$ | $7$ | ^ | ^ | -- | $11$ | ^ | | $13$ | $9$ | -- | -- | $p_i=-1$ | $1$, $3$, $5$, $7$, $9$, $11$ | **Offline testing** | | $14$ | $8$ | ^ | ^ | -- | $0$ -- $13$ | ^ |