First of all, each person has to be moved at most once. So, this problem is equivalent to the task of assigning each person the four statuses of either moving to the left end / moving to the right end / moving arbitrarily / never let them move. We will approach the problem with this premise.

First, let us fix an ordered set \(S=(S_1,S_2,\ldots,S_k)\) of people that will never be moved. Here, we assume \(S_1 \lt S_2 \lt \cdots \lt S_k\). Then we can see that:

• Let \(\text{pos}[i]\) be the initial position of the person \(i\) counted from the left. Then, it should hold that \(\text{pos}[S_1] \lt \text{pos}[S_2] \lt \cdots \lt \text{pos}[S_k]\).

Since every person in \(S\) does not move, it is obvious.

With more observation we can see the following three facts:

• Each person \(i\) such that \(S_1 \lt i \lt S_k\), \(i \notin S\) should be assigned the operation of being moved to an arbitrary position, paying cost \(A_i\).
• Each person \(i\) such that \(i \lt S_1\) can be assigned either operation of being moved to an arbitrary position with cost \(A_i\) or being moved to the left end with cost \(B_i\).
• Each person \(i\) such that \(S_k \lt i\) can be assigned either operation of being moved an arbitrary position with cost \(A_i\) or being moved to the right end with cost \(C_i\).

Based on these observations, we will perform a DP (Dynamic Programming) where \(\text{dp}[i]:=(\)the minimum sum of costs required to sort the people with indices less than or equal to \(i\), such that the maximum index of person in \(S\) is \(i)\). The transitions are as follows:

\[ dp[i]:=\min(\sum_{j=1}^{i-1}\min(A_j,B_j),\ \min_{j \lt i,\ pos[j] \lt pos[i]}(dp[j]+\sum_{k=j+1}^{i-1}A_k)) \]

The DP above costs \(O(N^2)\) naively, but it can be optimized to \(O(N \log N)\) by segment trees and cumulative sums.

Once the DP is processed, we can obtain the answer as \(\min_{1 \leq i \leq N}(dp[i]+\sum_{j=i+1}^{N} \min(A_j,C_j))\). Therefore we could solve the problem.

Note that \(S\) can never be empty in the optimal solution. If \(S\) is empty, there exists an integer \(i\ (0 \leq i \leq N)\) such that

• every person \(j\) such that \(j \leq i\) is assigned either operation of being moved to an arbitrary position with cost \(A_i\) or being moved to the left end with cost \(B_j\), and
• every person \(j\) such that \(i \lt j\) is assigned either operation of being moved to an arbitrary position with cost \(A_i\) or being moved to the right end with cost \(C_j\).

Here, one can add to \(S\) either of the person \(i\) or \(i+1\) that exists (or one of them if both exist) so that the total cost is strictly less than that of empty \(S\).

Sample Code (C++)

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
const ll inf = (1ll<<60);

ll op(ll a,ll b){
    return min(a,b);
}

ll e(){
    return inf;
}

int main(){
    int N; cin >> N;
    vector<int> P(N),A(N),B(N),C(N),pos(N+1);
    for(int i=0; i<N; i++){
        cin >> P[i];
        pos[P[i]] = i+1;
    }
    for(int i=0; i<N; i++) cin >> A[i] >> B[i] >> C[i];
    vector<ll> dp(N+1,inf),Asum(N+1),Bsum(N+1),Csum(N+1);
    segtree<ll,op,e> seg(N+1);
    ll ans = inf;
    for(int i=0; i<N; i++){
        Asum[i+1] = Asum[i]+A[i];
        Bsum[i+1] = Bsum[i]+min(B[i],A[i]);
        Csum[i+1] = Csum[i]+min(C[i],A[i]);
    }
    for(int i=1; i<=N; i++){
        dp[i] = min(Bsum[i-1],seg.prod(0,pos[i])+Asum[i-1]);
        ans = min(ans, dp[i]+Csum[N]-Csum[i]);
        seg.set(pos[i],dp[i]-Asum[i]);
    }
    cout << ans << endl;
}

Sample Code (Python)