#include #define FASTIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define int ll #define F first #define S second #define Bout(x) (x ? "Yes" : "No") #define DO(x) return x, void(0); using namespace std; using ll = long long; using ull = unsigned long long; using pii = pair; using vi = vector; using vii = vector; using mii = map; using ui = unsigned; const int N = 3e5 + 5; const int Md = 1e15 + 7; int n, m; int a[N], x[N], y[N]; struct LiChaoT { #define ls (id << 1) #define rs (id << 1 | 1) #define mid ((tl + tr) >> 1) struct node { int k, b; node(int _k = 0, int _b = 1e15) : k(_k), b(_b) { } int operator () (const int &x) const & { return k * x + b; } bool operator == (const node &T) const & { return k == T.k && b == T.b; } } seg[N << 2]; node cmp(node a, node b, int x) { if (a(x) - b(x) > 0) return b; if (b(x) - a(x) > 0) return a; return a; } void add(int id, int tl, int tr, node val, int l, int r) { if (l <= tl && tr <= r) { if (seg[id] == val) return; if (cmp(seg[id], val, mid) == val) swap(seg[id], val); if (cmp(seg[id], val, tl) == val) add(ls, tl, mid, val, l, r); if (cmp(seg[id], val, tr) == val) add(rs, mid + 1, tr, val, l, r); } else { if (l <= mid) add(ls, tl, mid, val, l, r); if (mid < r) add(rs, mid + 1, tr, val, l, r); } } node qry(int id, int tl, int tr, int x) { if (tl == tr) return seg[id]; node a = seg[id], b = (x <= mid ? qry(ls, tl, mid, x) : qry(rs, mid + 1, tr, x)); return cmp(a, b, x); } #undef mid #undef ls #undef rs }T; signed main() { FASTIO; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> x[i]; for (int i = 1; i <= n; i++) cin >> y[i]; T.add(1, 0, 2e5, { 1, y[0 + 1] - x[0 + 1] + 0 }, x[0 + 1], 2e5); T.add(1, 0, 2e5, { -1, y[0 + 1] + x[0 + 1] + 0 }, 0, x[0 + 1]); for (int i = 1; i <= n; i++) { int now = T.qry(1, 0, 2e5, a[i])(a[i]); T.add(1, 0, 2e5, { 1, y[i + 1] - x[i + 1] + now }, x[i + 1], 2e5); T.add(1, 0, 2e5, { -1, y[i + 1] + x[i + 1] + now }, 0, x[i + 1]); if (i == n) cout << now; } return 0; } /* a[i] : ppl x[i] : garbage X_i y[i] : garbage Y_i dp[i] = min(dp[j] + abs(x[j] - a[i]) + y[j]) x[i] < a[i] : min(dp[j] + a[i] - x[j] + y[j]) => min(a[i] + y[j] - x[j] + dp[j]) | x[i] -> N x[i] > a[i] : min(dp[j] + x[j] - a[i] + y[i]) => min(-a[i] + y[j] + x[j] + dp[j]) | 0 -> x[i] */