Minimum Cost to Make Sequence Good

You are given a sequence \(a\) of n non-negative integers: \(a_1,a_2,\dots,a_n\) and a cost array \(b\) where replacing element \(a_i\) costs \(b_i\) coins.

A sequence is defined as good if and only if there exists an integer \(k\) satisfying \(0\le k\le 10^6\) such that \[ a_i=a_1+(i-1)\,k,\quad \text{for all } 1\le i\le n. \]

To make the sequence good, for each \(i\) (\(1\le i\le n\)) you may either do nothing or pay \(b_i\) coins to replace \(a_i\) with any non-negative integer. Find the minimum total cost needed so that the final sequence is good.

Observation: If you decide on a particular progression defined by a starting value \(A\) (i.e. \(a_1 = A\)) and a common difference \(k\), then for each index \(i\) the final value should be \(A+(i-1)\,k\). If an element already equals this value, you incur no cost; otherwise, you pay \(b_i\) coins. Hence, if you let the total cost be

\[ \text{Cost}=\sum_{i=1}^{n}b_i-\sum_{\substack{1\le i\le n\\a_i=A+(i-1)\,k}}b_i, \]

minimizing the cost is equivalent to maximizing the total "saved" coins \(\sum_{\substack{1\le i\le n\\a_i=A+(i-1)\,k}}b_i\) over all choices of \(A\) and \(k\) (with \(0\le k\le10^6\)).

inputFormat

The first line contains an integer \(n\) (the length of the sequence).
The second line contains \(n\) space-separated non-negative integers \(a_1,a_2,\dots,a_n\).
The third line contains \(n\) space-separated integers \(b_1,b_2,\dots,b_n\) representing the cost to change each element.

outputFormat

Output a single integer representing the minimum total coins needed to make the sequence good.

sample

1
5
10

0