Problem J
Job Interview

Recently, a new company, Hyper Flex Technologies, decided to sponsor Prof. Halim’s CS3233 course and, as a result, received a large influx of applicants.

An interview was held to evaluate candidates for leadership abilities. Candidates enter the room one by one, in increasing order of skill level $A_i$, and form a line in the room.

When a new candidate arrives, they must partition the existing candidates into contiguous groups. The rightmost (newest) candidate picks their own group first. Then, the next rightmost ungrouped candidate becomes the new leader and picks their group, continuing until all candidates are grouped.

Each group contributes a conflict factor to the total score:

where $C$ is a constant, known as the chaos index. The new candidate’s score, $S_i$, is the sum of all conflict factors across groups, and their goal is to minimize their score.

The interviewers maintain a list of potential candidates in front of the interview room. After the $i$-th candidate is scored, they compute:

and modify the list accordingly. Specifically, the $B_i$-th candidate (1-indexed) is either added to or removed from the list: if the candidate is already on the list, they are removed; otherwise, they are added. (No one really knows how the interviewers judge candidates. But this is the blackbox pattern observed.)

Before entering the room, each candidate checks the list and avoids selecting leaders from it. Specifically, a candidate $i$ will not choose a group of the form $[j+1, j+2, \dots , i-1, i]$ if candidate $j$ is on the list. Since the list is only viewed before entering the room and they do not know the updated list, different candidates may have different sets of people they avoid when choosing their group during the partition process. (See sample explanation for better understanding.)

You are the last candidate — clearly the best — and you are anxious to know in advance what your score will be.

Input

The first line of input contains two integers $N, C$ ($1 \leq N \leq 500000, 0 \leq C \leq 10^{9}$), the number of candidates and the choas index.

The second line of input contains $N$ integers, $A_i$ ($0 \leq A_i \leq 10^{9}$, $ \forall i < N, A_i \leq A_{i+1}$) the skill level of the $i$-th candidate.

The third line of input contains $N$ integers, $K_i$ ($1 \leq K_i \leq i$).

Output

Output a single integer representing your score.

Sample Explanation

First candidate score: 1. With a group of $[1]$.

$B_1 = 1$, the candidate list becomes $\{ 1\} $, thus candidate $2$ cannot form group $[2]$.

Second candidate score: 5. With a group of $[1, 2]$, since candidate $2$ cannot choose $\{ 1\} $ as leaders and cannot form $[1], [2]$.

$B_2 = 1$, the candidate list becomes $\{ \} $, thus candidate $3$ has no restriction on what group to form.

Third candidate score: 6. With a group of $[1, 2], [3]$. Note that candidate $2$’s list remains $\{ 1\} $ and thus we cannot form $[1], [2], [3]$. Since after choosing group $[3]$, candidate $2$ will choose their group and it cannot be $[1, 2]$ as mentioned earlier.

$B_3 = 3$, the candidate list becomes $\{ 3\} $, thus candidate $4$ cannot form group $[4]$.

Repeating, we will get that the score of candidate $5$ is $9$ with $[1, 2], [3, 4, 5]$.

5 1
2 4 7 8 8 
1 1 2 1 3 

9