D. Размен

В стране $n$ номиналов монет $a_1 < a_2 < \dots < a_n$. Известно, что $a_1 = 1$ и каждый следующий номинал делится на предыдущий нацело.

Монет каждого номинала сколько угодно. Наберите сумму $S$ наименьшим числом монет.

Первая строка содержит число $n$ ($1 \le n \le 40$).

Вторая строка содержит $n$ номиналов, $1 \le a_i \le 10^{18}$.

Третья строка содержит число $S$ ($1 \le S \le 10^{18}$).

Одно число — наименьшее количество монет.