INF = (1 << 63) - 1 class ConvexHullTrick(): def __init__(self, xs): xs = sorted(set(xs)) self.n = len(xs) self.cx = {x : k for k, x in enumerate(xs)} self.log = (self.n - 1).bit_length() self.size = 1 << self.log self.e = (0, INF) self.x = xs + [INF] * (self.size - self.n) self.d = [self.e] * (2 * self.size) def val(self, line, x): a, b = line return a * x + b def _add_(self, line, p, lt, rt): while True: md = (lt + rt) // 2 lx = self.x[lt] mx = self.x[md] rx = self.x[rt - 1] lu = self.val(line, lx) < self.val(self.d[p], lx) mu = self.val(line, mx) < self.val(self.d[p], mx) ru = self.val(line, rx) < self.val(self.d[p], rx) if lu and ru: self.d[p] = line return if not lu and not ru: return if mu: self.d[p], line = line, self.d[p] if lu != mu: rt = md p = 2 * p else: lt = md p = 2 * p + 1 def add_line(self, line): self._add_(line, 1, 0, self.size) def add_seg(self, line, lt, rt): lx = self.cx[lt] + self.size rx = self.cx[rt] + self.size lt = self.cx[lt] rt = self.cx[rt] sz = 1 while lx < rx: if lx & 1: self._add_(line, lx, lt, lt + sz) lx += 1 lt += sz if rx & 1: rx -= 1 rt -= sz self._add_(line, rx, rt, rt + sz) lx >>= 1 rx >>= 1 sz <<= 1 def get_min(self, x): p = self.cx[x] + self.size res = INF while p: res = min(res, self.val(self.d[p], x)) p >>= 1 return res import sys input = sys.stdin.buffer.readline N = int(input()) A = list(map(int, input().split())) X = list(map(int, input().split())) Y = list(map(int, input().split())) cht = ConvexHullTrick(A) dp = [0] * (N + 1) for i in range(N): cht.add_line((-2 * X[i], dp[i] + X[i]**2 + Y[i]**2)) dp[i + 1] = cht.get_min(A[i]) + A[i]**2 print(dp[N])