#include "bits/stdc++.h" using namespace std; template static void amin(T &x, U y) { if (y < x) x = y; } const long long INFL = 0x3f3f3f3f3f3f3f3fLL;; struct DynamicRMQ { typedef long long Val; int n; vector d; void init(int nmin) { for (n = 1; n < nmin; n *= 2); d.assign(n * 2, INFL); } void update(int i, Val x) { d[n + i] = x; for (int k = (n + i) / 2; k > 0; k >>= 1) d[k] = min(d[k * 2], d[k * 2 + 1]); } Val get(int i) const { return d[n + i]; } //[l, r) Val query(int l, int r) const { Val m = INFL; for (; l && l + (l&-l) <= r; l += l & -l) m = min(m, d[(n + l) / (l&-l)]); for (; l < r; r -= r & -r) m = min(m, d[(n + r) / (r&-r) - 1]); return m; } }; int main() { int N; while (~scanf("%d", &N)) { vector as(N); for (int i = 0; i < N; ++ i) scanf("%d", &as[i]); vector xs(N); for (int i = 0; i < N; ++ i) scanf("%d", &xs[i]); vector ys(N); for (int i = 0; i < N; ++ i) scanf("%d", &ys[i]); auto values = xs; sort(values.begin(), values.end()); values.erase(unique(values.begin(), values.end()), values.end()); DynamicRMQ rmqL, rmqR; rmqL.init((int)values.size()); rmqR.init((int)values.size()); vector dp(N + 1, INFL); dp[0] = 0; for (int i = 0; i < N; ++ i) { { auto xi = (int)(lower_bound(values.begin(), values.end(), xs[i]) - values.begin()); rmqL.update(xi, min(dp[i] + ys[i] - xs[i], rmqL.get(xi))); rmqR.update(xi, min(dp[i] + ys[i] + xs[i], rmqR.get(xi))); } long long t = INFL; // for (int j = 0; j <= i; ++ j) // amin(t, dp[j] + abs(as[i] - xs[j]) + ys[j]); { auto xi = (int)(lower_bound(values.begin(), values.end(), as[i]) - values.begin()); amin(t, rmqL.query(0, xi) + as[i]); amin(t, rmqR.query(xi, (int)values.size()) - as[i]); } dp[i + 1] = t; } long long ans = dp[N]; printf("%lld\n", ans); } }