#include using namespace std; using int64 = long long; const int64 INF = 1LL << 58; template< typename Monoid > struct SegmentTree { using F = function< Monoid(Monoid, Monoid) >; int sz; vector< Monoid > seg; const F f; const Monoid M1; SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x) { seg[k + sz] = x; } void build() { for(int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } void update(int k, const Monoid &x) { k += sz; seg[k] = min(seg[k], x); while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid query(int a, int b) { Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } }; int main() { int64 N, A[300001]; int64 X[300001], Y[300001]; scanf("%lld", &N); for(int i = 0; i < N; i++) scanf("%lld", &A[i]); for(int i = 0; i < N; i++) scanf("%lld", &X[i]); for(int i = 0; i < N; i++) scanf("%lld", &Y[i]); /* vector< int64 > dp(N + 1, INF); dp[0] = 0; for(int i = 1; i <= N; i++) { int64 ret = INF; for(int j = i-1; j >= 0; j--) { int64 dist = dp[j] + abs(A[i - 1] - X[j]) + Y[j]; ret = min(ret, dist); } dp[i] = ret; } cout << dp[N] << endl; */ auto f = [&](int64 x, int64 y) { return min(x, y); }; SegmentTree< int64 > latte(N + 1, f, INF), malta(N + 1, f, INF); auto update = [&](int idx, int64 v) { auto it = lower_bound(A, A + N, X[idx]) - A; latte.update(it, v + Y[idx] + X[idx]); malta.update(it, v + Y[idx] - X[idx]); }; update(0, 0); for(int i = 1; i <= N; i++) { int64 ret = min(latte.query(i, N + 1) - A[i - 1], malta.query(0, i) + A[i - 1]); // dp[i] = (dp[j]+Y[j]+X[j])-A[i-1] (A[i-1]≦X[j]) // (dp[j]+Y[j]-X[j])+A[i-1] (A[i-1]≧X[j]) if(i == N) cout << ret << endl; else update(i, ret); } }