AT_abc201_f Insertion Sort

There are $N$ people, who are given ID numbers $1$ through $N$, standing in a row from left to right. Initially, the ID number of the $i$\-th person from the left is $P_i$. Your objective is to rearrange the people in ascending order of the ID number from left to right, by repeatedly doing the three kinds of operations below. You can do these operations any number of times (possibly zero) in any order. - Choose an integer $i\ (1 \leq i \leq N)$, pay the cost $A_i$, and move Person $i$ (the person with the ID number $i$) to any position of your choice. - Choose an integer $i\ (1 \leq i \leq N)$, pay the cost $B_i$, and move Person $i$ to the left end of the row. - Choose an integer $i\ (1 \leq i \leq N)$, pay the cost $C_i$, and move Person $i$ to the right end of the row. Minimize the total cost you pay before achieving the objective.

Input is given from Standard Input in the following format: $N$ $P_1$ $P_2$ $\ldots$ $P_N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$

Print the minimum total cost you need to pay before achieving the objective.

- $1 \leq N \leq 2 \times 10^5$ - $1 \leq P_i \leq N$ - $1 \leq A_i,B_i,C_i \leq 10^9$ - $P_i \neq P_j\ (i \neq j)$ - All values in input are integers.