中文翻译：

有一个长度为$n$的非负整数序列$a(0\leq a_i\leq 10^6)$，你可以花费$b_i$的代价把$a_i$改成任意非负整数。

问：最少多少的代价可以把$a$数组修改成从左到右，公差在$[0,10^6]$的等差数列。

$n\leq 2\times 10^5$。

题目描述

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

A sequence is defined as 'good' if and only if there exists a non negative integer $k(0\leq k\leq 10^6)$ that satisfies the following 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 do nothing, or pay $b_i$ coin to replace $a_i$ with any non-negative integer.

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

输入格式

The first line contains an integer $n(1\leq n\leq 2\times 10^5)$, described in the 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)$.

输出格式

One integer, the answer.

5
1 4 3 2 5
1 1 1 1 1

2

5
1 4 3 2 5
1 9 1 1 1

3