| Codeforces Round 236 (Div. 2) |
|---|
| Закончено |
У вас есть массив целых положительных чисел a[1], a[2], ..., a[n], а также множество плохих простых чисел b1, b2, ..., bm. Простые числа, которые не встречаются в множестве b считаются хорошими. Красотой массива a назовем сумму 
, где функция f(s) определяется следующим образом:
- f(1) = 0;
- Пусть p — минимальный простой делитель числа s. Если p — хорошее простое число, то
, иначе 
.
Вам разрешено последовательно провести произвольное (возможно, ноль) количество операций улучшения массива a. Операцией улучшения назовем следующую последовательность действий:
- Выбрать некоторое число r (1 ≤ r ≤ n) и подсчитать значение g = НОД(a[1], a[2], ..., a[r]).
- Выполнить присвоения:
, 
, ..., 
.
Какую максимальную красоту массива вы сможете получить?
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 5000) — количество чисел в массиве a и количество плохих простых чисел.
Во второй строке заданы n целых чисел через пробел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — массив a. В третьей строке заданы m целых чисел через пробел b1, b2, ..., bm (2 ≤ b1 < b2 < ... < bm ≤ 109) — множество плохих простых чисел.
Выведите единственное целое число — ответ на задачу.
5 2
4 20 34 10 10
2 5
-2
4 5
2 4 8 16
3 5 7 11 17
10
Обратите внимание, что ответ на задачу может быть отрицательным числом.
НОД(x1, x2, ..., xk) обозначает наибольшее целое положительное число, которое делит каждое xi без остатка.
