Adding the Exponents

Interview

Time limit1sMemory limit128 MB

Summary

Given N distinct primes and K up to 10^12, find the sum over i from 1 to K of how many times the primes in P divide i, counted with multiplicity.

Level: Medium4 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

A set $P=\{p_1, p_2, \cdots, p_N\}$ consists of $N$ distinct primes.

For a positive integer $i$ , let $b_i$ be the maximum value of $\sum_{j=1}^{N}{a_j}$ such that $\frac{i}{p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_N^{a_N}}$ is a positive integer. ( $a_j$ is an integer.)

Given the set $P$ and a positive integer $K$ , find the value of $\sum_{i=1}^{K} b_{i}$ .

Input

The first line contains $N$ ( $1\leq N \leq 200\,000$ ), the number of elements in $P$ .

The second line contains $N$ distinct primes $p$ ( $1\leq p \leq 3\times 10^{6}$ ) separated by spaces, the elements of $P$ .

The third line contains a positive integer $K$ ( $1\leq K \leq 10^{12}$ ).

Output

Print the value of $\sum_{i=1}^{K} b_{i}$ .

Examples1

Example 1
Input
```
2
2 3
100
```
Expected output
```
145
```