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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

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

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

Output

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

Constraints

\(1 \le n \le 10^5\),

\(2 \le a_i \le 10^5\),

\(1 \le u_i, d_i \le 10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 2 3 4 1 4 1 2 4 3	3

Notes

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