Полив по расписанию

У Саши на подоконнике стоит N растений. Для каждого растения он завёл правило: если период этого растения равен p, то Саша поливает его в каждый день с номером, который делится на p (то есть в дни p, 2p, 3p, ...).

Саша хочет понять, сколько раз всего он возьмёт лейку за первые D дней (считаем дни пронумерованными от 1 до D).

Посчитайте общее число поливов всех растений за дни 1..D.

Формат ввода

Первая строка: два целых числа N и D. Вторая строка: N целых чисел p1, p2, ..., pN — периоды растений.

Формат вывода

Выведите одно целое число — общее количество поливов.

Ограничения

• 1 ≤ N ≤ 2000
• 1 ≤ D ≤ 100000
• 1 ≤ pi ≤ 100000

Пример

Ввод:

3 10
2 3 5

Вывод:

10

Пояснение: за 10 дней растение с периодом 2 поливают 5 раз, с периодом 3 — 3 раза, с периодом 5 — 2 раза. Итого 10.

Ключевое наблюдение: растение с периодом p поливают ровно в дни p, 2p, 3p, … Пока номер дня не превысит D. Значит, нужно понять, сколько таких кратных поместится в диапазон 1..D.

Приём: «подсчёт кратных через деление нацело». Он работает, потому что целая часть от D / p как раз и есть максимальное k, для которого k*p ≤ D. То есть это количество поливов одного растения.

План решения:

• Прочитать N и D.
• Прочитать список периодов p1..pN.
• Завести ответ total = 0.
• Для каждого p:
• добавить к ответу D // p.
• Вывести total.

Мини-сниппет формулы:

• поливов для одного растения: cnt = D // p
• общий ответ: сумма этих cnt.

Сложность: O(N) по времени и O(1) доп.памяти (кроме хранения списка). При N ≤ 2000 это мгновенно.

Частая ошибка: пытаться симулировать по дням и отмечать, какие растения поливать (O(N*D) до 2e8 операций) — это слишком медленно и здесь не нужно.