Problem Statement

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.

Constraints

• $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.

Input

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

Output

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