/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
1 から N までの番号が振られた N 人の人が左右一列に並んでいます。はじめ、左から i 番目の人の番号は P_i です。
あなたの目標は、以下の 3 種類の操作を繰り返すことで人々が左から番号の昇順で並んでいるようにすることです。これらの操作は、任意の順に何回でも（0 回でもよい）行うことができます。
- 整数 i\ (1 \leq i \leq N) を選ぶ。コスト A_i を払い、人 i を好きな位置に移動させる。
- 整数 i\ (1 \leq i \leq N) を選ぶ。コスト B_i を払い、人 i を左端に移動させる。
- 整数 i\ (1 \leq i \leq N) を選ぶ。コスト C_i を払い、人 i を右端に移動させる。
目標を達成するまでに支払う合計コストを最小化してください。
制約
- 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)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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
出力
目標を達成するまでに支払う合計コストの最小値を出力せよ。
入力例 1
3 3 1 2 9 3 5 8 6 4 9 4 6
出力例 1
6
コスト C_3=6 を払って人 3 を右端に動かすことで、人々を昇順に並び替えることができます。
これより合計コストが低い並び替え方は存在しないので、答えは 6 となります。
入力例 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
出力例 2
15
以下の順に操作を行うことで最小値を達成可能です。
- コスト B_1=8 を払い、人 1 を左端に移動させる。
- コスト C_5=5 を払い、人 5 を右端に移動させる。
- コスト C_6=2 を払い、人 6 を右端に移動させる。
入力例 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
出力例 3
15865
入力例 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
出力例 4
20637
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