Щасливий набір чисел

Обмеження: 2 сек., 256 МіБ

Зеник має набір з $n$ цілих чисел. Марічка може видалити $i$-те число і заплатити за це $d_i$ щасливих монет, проте вона не може видалити усі числа. Після цього Зеник може збільшити числа, за збільшення $i$-го числа на 1 потрібно заплатити $u_i$ монет. Зауважте, що він може збільшити те саме число декілька раз.

Вони вирішили такими діями зробити набір чисел, найбільший спільний дільник яких більший за 1, тобто існує таке $x > 1$, що кожне число в кінцевому наборі ділиться націло на $x$. Зауважте, що кінцевий набір може містити одне число.

Знайдіть яку мінімальну кількість щасливих монет потрібно заплатити, щоб досягнути цілі.

Вхідні дані

У першому рядку задано одне ціле число $n$ — початкова кількість чисел.

У другому рядку задано $n$ цілих чисел $a_i$ — початкові числа.

У третьому рядку задано $n$ цілих чисел $u_i$ — кількість монет, яку треба заплатити за збільшення числа на 1.

У останньому рядку задано $n$ цілих чисел $d_i$ — кількість монет, яку треба заплатити за видалення числа.

Вихідні дані

У єдиному рядку виведіть одне ціле число — мінімальну кількість монет, що мають заплатити Зеник з Марічкою.

Обмеження

$1 \le n \le 10^5$,

$2 \le a_i \le 10^5$,

$1 \le u_i, d_i \le 10^6$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 2 3 4 1 4 1 2 4 3	3

Примітки

У прикладі оптимально збільшити перше число на 1, а третє число двічі збільшити на 1 і вкінці отримати набір із двох трійок і шестірки, заплативши сумарно 3 монети.