AT_abc201_f [ABC201F] Insertion Sort

[problemUrl]: https://atcoder.jp/contests/abc201/tasks/abc201_f $ 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 $ を右端に移動させる。 目標を達成するまでに支払う合計コストを最小化してください。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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) $ - 入力は全て整数 ### Sample Explanation 1 コスト $ C_3=6 $ を払って人 $ 3 $ を右端に動かすことで、人々を昇順に並び替えることができます。 これより合計コストが低い並び替え方は存在しないので、答えは $ 6 $ となります。 ### Sample Explanation 2 以下の順に操作を行うことで最小値を達成可能です。 - コスト $ B_1=8 $ を払い、人 $ 1 $ を左端に移動させる。 - コスト $ C_5=5 $ を払い、人 $ 5 $ を右端に移動させる。 - コスト $ C_6=2 $ を払い、人 $ 6 $ を右端に移動させる。