#include #include #include using namespace std; #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define MOD 1000000007 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double #define int long long const int MAX_N = 500005; const int MAX_K = 500005; class Node { public: Node(LL v = unitValue) : value(v) { } Node operator + (const Node& monoid) const { return Node(min(this->getValue(), monoid.getValue())); } static Node unit() { return Node(unitValue); } void setValue(LL l) { this->value = l; } LL getValue() const { return this->value; } private: LL value; static const LL unitValue = INF_INT_MAX; }; template class SegmentTree { public: SegmentTree(int size) { init(size); } void init(int size) { vec.clear(); k = 1; while(k < size) { k *= 2; } for(int i = 0; i < 2*k; i++) { vec.push_back(T::unit()); } } void update(int i, T x) { //iをxに変更する i += k-1; vec[i] = x; while(i > 0) { i = (i-1)/2; vec[i] = vec[i*2+1] + vec[i*2+2]; } } T find(int l, int r) { return _find(l, r, 0, 0, k); } private: vector vec; int k; T _find(int l, int r, int k, int x, int y) { if (r <= x || y <= l) { //重なってない場合 return T::unit(); } else if (l <= x && y <= r) { //完全にかぶってる場合 return vec[k]; } else { //中途半端にかぶってる場合 int mid = (x+y)/2; T lNode = _find(l, r, 2*k+1, x, mid); T rNode = _find(l, r, 2*k+2, mid, y); return lNode + rNode; } } }; int N; int A[MAX_N]; int X[MAX_N]; int Y[MAX_N]; int dp[MAX_N]; signed main() { cin >> N; for(int i = 0; i < N; i++) { cin >> A[i]; } for(int i = 0; i < N; i++) { cin >> X[i]; } for(int i = 0; i < N; i++) { cin >> Y[i]; } SegmentTree segtree1(MAX_N), segtree2(MAX_N); for(int i = 0; i < N; i++) { segtree1.update(i, dp[i] + Y[i] + X[i]); segtree2.update(i, dp[i] + Y[i] - X[i]); if(i >= 1) { int l = lower_bound(X, X+i+1, A[i]) - X; dp[i+1] = min(segtree1.find(l, MAX_N).getValue() - A[i], segtree2.find(0, l).getValue() + A[i]); } else { dp[1] = abs(X[0] - A[0]) + Y[0]; } } cout << dp[N] << endl; return 0; }