102015: [AtCoder]ABC201 F - Insertion Sort
Description
Score : $600$ points
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.
Sample Input 1
3 3 1 2 9 3 5 8 6 4 9 4 6
Sample Output 1
6
You can rearrange the people in ascending order of the ID number by paying the cost $C_3=6$ to move Person $3$ to the right end.
There is no way to rearrange the people that costs less, so the answer is $6$.
Sample Input 2
6 2 6 5 3 4 1 10 8 16 30 2 10 10 17 8 11 27 22 8 6 5 15 29 2
Sample Output 2
15
The following sequence of operations minimizes the total cost:
- pay the cost $B_1=8$ to move Person $1$ to the left end;
- pay the cost $C_5=5$ to move Person $5$ to the right end;
- pay the cost $C_6=2$ to move Person $6$ to the right end.
Sample Input 3
9 3 8 4 7 6 9 1 5 2 7976 3696 9706 768 8807 8521 1133 8683 7120 1189 3331 2259 900 7451 1159 6126 2639 7107 5540 8253 2891 8417 4220 9091 8732 1417 1540
Sample Output 3
15865
Sample Input 4
12 11 9 1 12 2 7 3 5 10 4 6 8 3960 3158 9029 6521 6597 7581 5688 2299 2123 4946 4298 9122 394 4350 9142 3098 7151 2039 8525 3758 6155 6970 3658 9353 9780 1778 3608 6065 5562 923 9701 5524 6482 9395 6016 705
Sample Output 4
20637