Hamming Sequence

Time limit1sMemory limit128 MB

Summary

Given three primes and an index i, find the i-th smallest number greater than 1 whose prime factors all lie among those three primes.

Level: Hard8 of 10
Topics: Math, Number theory, Binary search, Combinatorics
Solved: No attempts yet

Problem

For three primes $p_1$ , $p_2$ , $p_3$ , define the Hamming sequence $H(p_1, p_2, p_3)$ .

$H(p_1, p_2, p_3)$ is the ascending list of natural numbers greater than $1$ whose only prime factors are among $p_1$ , $p_2$ , $p_3$ . (In particular, $1$ is not included.)

For example, $H(2, 3, 5) = 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, \dots$ , and its fifth number is $6$ .

Input

The first line contains $p_1$ , $p_2$ , $p_3$ , and $i$ . All four integers are less than $10^{18}$ .

Output

Print the $i$ -th number of $H(p_1, p_2, p_3)$ . The printed number is less than $10^{18}$ .

Examples3

Example 1
Input
```
7 13 19 100
```
Expected output
```
26590291
```
Example 2
Input
```
2 3 5 5
```
Expected output
```
6
```
Example 3
Input
```
2 3 5 1
```
Expected output
```
2
```