지수를 더하자

서로 다른 $N$개의 소수로 이루어진 집합 $P=\{p_1, p_2, \cdots, p_N\}$이 있다.

양의 정수 $i$에 대하여 $\frac{i}{p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_N^{a_N}}$의 값이 양의 정수가 되도록 하는 $\sum_{j=1}^{N}{a_j}$의 최댓값을 $b_i$라고 하자. (단, $a_j$는 정수이다.)

집합 $P$와 양의 정수 $K$가 주어질 때, $\sum_{i=1}^{K} b_{i}$의 값을 구하시오.

첫째 줄에 집합 $P$의 원소의 개수 $N\left(1\leq N \leq 200\,000\right)$가 주어진다.

둘째 줄에 집합 $P$를 이루는 서로 다른 $N$개의 소수 $p\left(1\leq p \leq 3\times 10^{6}\right)$가 공백으로 구분되어 주어진다.

셋째 줄에 양의 정수 $K\left(1\leq K \leq 10^{12}\right)$가 주어진다.

$\sum_{i=1}^{K} b_{i}$의 값을 출력하시오.