Задача №114098. Автобусы

В Берляндии плачевная ситуация с междугородним автобусным сообщением. Во всей стране есть всего три автобусных маршрута, по каждому из которых курсирует лишь один автобус. В первый день нового года ровно в полночь все три автобуса отправляются по своим маршрутам из столицы Берляндии. Известно, что первому автобусу на то, чтобы проехать весь маршрут и вернуться в столицу требуется \(a\) минут, второму — \(b\) минут, а третьему — \(c\) минут. Таким образом, первый автобус отправляется из столицы Берляндии в моменты времени \(0, a, 2a, 3a, \ldots\), второй — в моменты времени \(0, b, 2b, 3b, \ldots\), а третий в моменты времени \(0, c, 2c, 3c, \ldots\).

Момент времени называется подходящим для пересадки , если в этот момент все три автобуса отправляются из столицы Берляндии. Например если \(a = 1\), \(b = 2\), \(c = 1\), то моменты времени \(0\) и \(2\) являются подходящими для пересадки, а момент времени \(1\) не является, потому что в этот момент времени второй автобус находится в пути. Берляндия — особая страна с особым измерением времени, поэтому в берляндских сутках ровно \(t\) минут. Это означает, что в первый день происходят все моменты времени с 0-го по \((t - 1)\)-й включительно, во второй день — c \(t\)-го по \((2t - 1)\)-й включительно, в третий — с \(2t\)-го по \((3t - 1)\)-й включительно и так далее.

Министерство транспорта Берляндии заинтересовалось, сколько подходящих для пересадки моментов времени произойдёт в \(d\)-й день в Берляндии. К сожалению, местные чиновники заняты другими делами, поэтому ответить на этот вопрос было поручено вам.

Входные данные

В пяти строках заданы пять целых чисел \(a, b, c, t\) и \(d\) (\(1 \le a, b, c \le 10^6, 1 \le t, d \le 10^9\)) — время полного прохождения маршрута первым, вторым и третьим автобусами, соответственно, количество минут в сутках и номер дня, которым интересуется министерство транспорта Берляндии.

Выходные данные

Выведите одно целое число — количество подходящих для пересадки моментов времени в \(d\)-й день.

Примечание

В первом примере сутки длятся \(3\) минуты, поэтому все моменты времени в день с номером \(1\) — это \(0\), \(1\), \(2\), из них моменты времени \(0\) и \(2\) являются подходящими для пересадки.

Во втором примере рассматриваются вторые сутки с моментами времени \(7\), \(8\), \(9\), \(10\), \(11\), \(12\), \(13\). Первый автобус отправляется в моменты времени \(8\), \(10\), \(12\), второй автобус — в моменты времени \(9\) и \(12\), а третий — в моменты времени \(8\) и \(12\). Таким образом, только момент времени \(12\) является подходящим для пересадки.

В третьем примере нет ни одного подходящего для пересадки момента времени.

Система оценки

В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на первых \(35\) тестах будут доступны во время соревнования. Результаты работы на остальных \(15\) будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq a, b, c, t, d \leq 100\), наберут не менее \(20\) баллов.

Решения, корректно работающие при \(t = 1\), наберут не менее \(10\) баллов.

Решения, корректно работающие при \(1 \leq t \leq 10^6\), наберут не менее \(50\) баллов.

Решения, корректно работающие при \(d = 1\), наберут не менее \(20\) баллов.

Примеры
Входные данные
1
2
1
3
1
Выходные данные
2
Входные данные
2
3
4
7
2
Выходные данные
1
Входные данные
2
3
4
3
3
Выходные данные
0
Сдать: для сдачи задач необходимо войти в систему