Щасливий набір чисел
Обмеження: 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 монети.
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|