#include #include const long long sup = 1LL << 60; typedef struct { long long key; int id; } data; typedef struct { data obj[100001]; int size; } min_heap; void push(min_heap* h, data x) { int i = ++(h->size), j = i >> 1; data tmp; h->obj[i] = x; while (j > 0) { if (h->obj[i].key < h->obj[j].key) { tmp = h->obj[j]; h->obj[j] = h->obj[i]; h->obj[i] = tmp; i = j; j >>= 1; } else break; } } data pop(min_heap* h) { int i = 1, j = 2; data output = h->obj[1], tmp; h->obj[1] = h->obj[(h->size)--]; while (j <= h->size) { if (j < h->size && h->obj[j^1].key < h->obj[j].key) j ^= 1; if (h->obj[j].key < h->obj[i].key) { tmp = h->obj[j]; h->obj[j] = h->obj[i]; h->obj[i] = tmp; i = j; j <<= 1; } else break; } return output; } long long solve(int N, int X[], int A[]) { if (N == 1) { if (A[1] == 1) return 0; else return -1; } int i, D[201], A_max = 0; for (i = 2; i <= N; i++) D[i] = X[i] - X[i-1]; for (i = 1; i <= N; i++) if (A_max < A[i]) A_max = A[i]; A_max *= 2; int j, jj, k, kk, kkk, cur, prev, L[100001], R[100001], tail; long long dp[2][3][10001], tmp, Y[100001]; data d; min_heap h[3][2], hh; for (j = 0; j <= 2; j++) for (k = 0; k <= A_max; k++) dp[0][j][k] = sup; dp[0][0][A[1]*2] = 0; dp[0][1][A[1]*2-1] = 0; dp[0][2][A[1]*2-2] = 0; for (i = 2, cur = 1, prev = 0; i <= N; i++, cur ^= 1, prev ^= 1) { for (j = 0, tail = 0; j <= 2; j++) for (k = 0; k <= 1; k++) h[j][k].size = 0; for (j = 0; j <= 2; j++) { for (k = 1; k <= A_max; k++) { if (dp[prev][j][k] == sup) continue; tmp = dp[prev][j][k] + (long long)k * D[i]; for (jj = 0; jj <= 2 - j; jj++) { Y[tail] = tmp; kk = A[i] * 2 - jj; kkk = 0; R[tail] = k + kk - kkk; kkk = A[i] * 2 - jj; if (kkk > k) kkk = k; kk = A[i] * 2 - jj - kkk; L[tail] = k + kk - kkk; d.key = L[tail]; d.id = tail; push(&(h[j+jj][abs(L[tail])%2]), d); tail++; } } } for (j = 0; j <= 2; j++) { for (k = 0, hh.size = 0; k <= A_max; k += 2) { while (h[j][0].size > 0 && h[j][0].obj[1].key <= k) { d = pop(&(h[j][0])); d.key = Y[d.id]; push(&hh, d); } while (hh.size > 0 && R[hh.obj[1].id] < k) pop(&hh); if (hh.size > 0) dp[cur][j][k] = hh.obj[1].key; else dp[cur][j][k] = sup; } for (k = 1, hh.size = 0; k <= A_max; k += 2) { while (h[j][1].size > 0 && h[j][1].obj[1].key <= k) { d = pop(&(h[j][1])); d.key = Y[d.id]; push(&hh, d); } while (hh.size > 0 && R[hh.obj[1].id] < k) pop(&hh); if (hh.size > 0) dp[cur][j][k] = hh.obj[1].key; else dp[cur][j][k] = sup; } } } if (dp[prev][2][0] == sup) return -1; else return dp[prev][2][0]; } int main() { int i, N, X[201], A[201], A_max = 0; scanf("%d", &N); for (i = 1; i <= N; i++) scanf("%d", &(X[i])); for (i = 1; i <= N; i++) scanf("%d", &(A[i])); printf("%lld\n", solve(N, X, A)); fflush(stdout); return 0; }