F. Lotes no anel

Time limit: 6000 msMemory limit: 256 MB

Há $n$ depósitos em um anel. O depósito $i$ contém $a_i$ unidades indivisíveis de um produto. Uma operação transporta uma unidade entre depósitos vizinhos, em qualquer sentido. A ligação entre $i$ e $i+1$ custa $c_i$ por unidade transportada; a ligação $n$ conecta $n$ a $1$ .

Você deve escolher um inteiro $q \ge 2$ e redistribuir as unidades de modo que, ao final, a quantidade em cada depósito seja múltipla de $q$ . Zero é múltiplo de qualquer $q$ . Não se pode criar nem destruir unidades, e só é possível retirar uma unidade de um depósito que a possua.

Determine o menor custo total, considerando todas as escolhas de $q$ e todas as redistribuições possíveis, ou informe que isso é impossível.

Input

A primeira linha contém $n$ ( $3 \le n \le 200000$ ). A segunda contém $n$ inteiros $a_i$ (), com . A terceira contém inteiros ().

Output

Imprima o menor custo total, ou -1 se for impossível.

Samples

Sample 1

Input

3
1 1 1
1 10 1

Output

Escolha $q=3$ e transporte as unidades dos depósitos $2$ e $3$ para o depósito $1$ , usando as duas ligações de custo $1$ .