import bisect class SegmentTree: def __init__(self, size): self.n = 1 while self.n < size: self.n <<= 1 self.size = size self.tree = [float('inf')] * (2 * self.n) def update(self, pos, value): pos += self.n self.tree[pos] = value while pos > 1: pos >>= 1 left = self.tree[pos << 1] right_val = self.tree[(pos << 1) + 1] self.tree[pos] = min(left, right_val) def query_min(self, l, r): res = float('inf') l += self.n r += self.n while l <= r: if l % 2 == 1: res = min(res, self.tree[l]) l += 1 if r % 2 == 0: res = min(res, self.tree[r]) r -= 1 l >>= 1 r >>= 1 return res def main(): import sys input = sys.stdin.read().split() ptr = 0 n = int(input[ptr]) ptr += 1 a = list(map(int, input[ptr:ptr + n])) ptr += n x = list(map(int, input[ptr:ptr + n])) ptr += n y = list(map(int, input[ptr:ptr + n])) ptr += n cum_min_A = [0] * n DP = [0] * n st = SegmentTree(n) for i in range(n): prev = DP[i-1] if i > 0 else 0 A_i = prev - x[i] + y[i] if i == 0: cum_min_A[i] = A_i else: cum_min_A[i] = min(cum_min_A[i-1], A_i) B_i = prev + x[i] + y[i] st.update(i, B_i) a_i = a[i] m_i = bisect.bisect_right(x, a_i) - 1 candidate_A = cum_min_A[m_i] + a_i if m_i >= 0 else float('inf') left = m_i + 1 right = i if left > right: candidate_B = float('inf') else: min_b = st.query_min(left, right) candidate_B = min_b - a_i DP_i = min(candidate_A, candidate_B) DP[i] = DP_i print(DP[-1]) if __name__ == '__main__': main()