#include #define rep(i,n) for(int i = 0; i < (n); i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pb push_back #define eb emplace_back using namespace std; template using V = vector; template using VV = V>; using ll = long long; using ld = long double; using pii = pair; using pll = pair; using pdd = pair; const ll INF = 1e18; struct LiChaoTree{ int size; vector seg; LiChaoTree(){} LiChaoTree(int size){ this->size = size; seg.resize(1<<(size+1)); } void init() { for(int i = 0; i < (1<<(size+1)); i++) seg[i] = make_pair(0, INF); } ll calc(pll f, ll x) { return f.first * x + f.second; } ll query(int x) //xにおける最小値を取得 { int i = x + (1 << size); ll ret = INF; while(i >= 1){ ret = min(ret, calc(seg[i], x)); i /= 2; } return ret; } void add(int k, int l, int r, pll f) { int m = (l+r)/2; if(calc(f, m) < calc(seg[k], m)) swap(seg[k], f); bool L = (calc(f, l) < calc(seg[k], l)), R = (calc(f, r) < calc(seg[k], r)); if(L == R) return; if(L) add(k*2, l, m, f); if(R) add(k*2+1, m+1, r, f); } void addSegment(int a, int b, int k, int l, int r, pll f) { if(b < l || r < a) return; if(a <= l && r <= b){ add(k, l, r, f); return; } addSegment(a, b, k*2, l, (l+r)/2, f); addSegment(a, b, k*2+1, (l+r)/2+1, r, f); } void addSegment(int a, int b, ll p, ll q) //区間[a, b]に線分px+qを追加 { addSegment(a, b, 1, 0, (1<> n; V a(n), x(n), y(n); rep(i,n) cin >> a[n-1-i]; rep(i,n) cin >> x[n-1-i]; rep(i,n) cin >> y[n-1-i]; LiChaoTree lct(20); lct.init(); V dp(n+1); dp[0] = 0; lct.addSegment(a[0], (1<<20)-1, 1, -a[0]+dp[0]); lct.addSegment(0, a[0]-1, -1, a[0]+dp[0]); for(int i = 1; i <= n; i++){ dp[i] = lct.query(x[i-1]) + y[i-1]; if(i < n){ lct.addSegment(a[i], (1<<20)-1, 1, -a[i]+dp[i]); lct.addSegment(0, a[i]-1, -1, a[i]+dp[i]); } } cout << dp[n] << endl; }