27725번 - 지수를 더하자

서로 다른 $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}$의 값을 출력하시오.