#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define int long long int MOD = 1000000007; template struct segtree { const int inf = (int)1 << 60; int N; int dat[700000]; segtree() {} segtree(int n) { N = 1; while (N < n) N *= 2; for (int i = 0; i < 2 * N - 1; i++) dat[i] = inf; } // update k th element void update(int k, int a) { k += N - 1; // leaf dat[k] = a; while (k > 0) { k = (k - 1) / 2; dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); } } // min [a, b) int query(int a, int b) { return query(a, b, 0, 0, N); } int query(int a, int b, int k, int l, int r) { if (r <= a or b <= l) return inf; if (a <= l and r <= b) return dat[k]; int m = (l + r) / 2; return min(query(a, b, k * 2 + 1, l, m), query(a, b, k * 2 + 2, m, r)); } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector A(N); vector X(N); vector Y(N); vector dp(N + 1, 0); int res = 0; for (int i = 0; i < N; i++) { cin >> A[i]; A[i]++; } for (int i = 0; i < N; i++) { cin >> X[i]; X[i]++; } for (int i = 0; i < N; i++) { cin >> Y[i]; //Y[i]++; } segtree sg1(N); segtree sg2(N); dp[0] = 0; sg1.update(0, dp[0] - X[0] + Y[0]); sg2.update(0, dp[0] + X[0] + Y[0]); X.push_back(1 << 30); //sg1.update() for (int i = 1; i <= N; i++) { int t = lower_bound(X.begin(), X.end(), A[i - 1]) - X.begin(); int a; if (i <= t) { a = sg1.query(0, i) + A[i - 1]; } else { a = sg1.query(0, t) + A[i - 1]; a = min(a, sg2.query(t, i) - A[i - 1]); } dp[i] = a; if (i < N) { sg1.update(i, dp[i] - X[i] + Y[i]); sg2.update(i, dp[i] + X[i] + Y[i]); } } cout << dp[N] << endl; }