Problem Description

Given a sequence \( a \) of non-negative integers of length \( n \), where the \( i \)-th element is \( a_i \) ( \( 1 \leq i \leq n \) ).

A sequence is considered 'good' if and only if there exists a non-negative integer \( k \) ( \( 0 \leq k \leq 10^6 \) ) that satisfies the condition:

\( a_i = a_1 + (i-1)k \) for all \( 1 \leq i \leq n \).

To make this sequence 'good', for each \( i \) ( \( 1 \leq i \leq n \) ), you can either do nothing or pay \( b_i \) coins to replace \( a_i \) with any non-negative integer.

The question is, what is the minimum cost to make this sequence 'good'.

Input Format

The first line contains an integer \( n \) ( \( 1 \leq n \leq 2 \times 10^5 \) ), as described in the problem statement.

The second line contains \( n \) integers \( a_1, ..., a_n \) ( \( 0 \leq a_i \leq 10^6 \) ).

The third line contains \( n \) integers \( b_1, ..., b_n \) ( \( 0 \leq b_i \leq 10^6 \) ).

Output Format

One integer, representing the minimum cost to make the sequence 'good'.

Sample Input and Output

Sample Input #1

5
1 4 3 2 5
1 1 1 1 1

Sample Output #1

2

Sample Input #2

5
1 4 3 2 5
1 9 1 1 1

Sample Output #2

3

见题面 Input 部分

见题面 Output 部分