D. Улучшаем массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У вас есть массив целых положительных чисел 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 без остатка.