K-th Largest N-Pseudo-Smooth Number

An integer \(M>1\) with prime factorization (with multiplicities) \(M = \prod_{i=1}^n p_i^{c_i}\) is said to have a total of \(k = \sum_{i=1}^n c_i\) prime factors. Let \(a_k\) be the largest prime factor in the factorization. We call \(M\) an \(N\)-pseudo-smooth number if it satisfies the following conditions:

• \(a_k < 128\), and
• \(a_k^{k} \le N\) (in \(\LaTeX\) format, this is \(a_k^{k} \leq N\)).

For a given \(N\) and a positive integer \(K\), your task is to determine the \(K\)th largest \(N\)-pseudo-smooth number. Note: The "\(K\)th largest" means that if you list all \(N\)-pseudo-smooth numbers in descending order, the first element is the largest, the second element is the second largest, and so on.

Example: Consider \(N=10\). The possible \(N\)-pseudo-smooth numbers are calculated as follows.
Using only the prime 2: Since the condition \(2^{k} \le 10\) gives \(k \le 3\), we obtain \(2, 4, 8\).
Using 3: \(3^{1}=3\) and \(3^{2}=9\) are allowed.
Using a combination of 2 and 3: For \(2^1 \times 3^1=6\), we have \(k=2\) and the maximum prime is 3; indeed \(3^2=9 \le 10\).
Also, primes 5 and 7 yield valid numbers \(5\) and \(7\) (with \(k=1\)).
Thus, the set of valid numbers is \(\{2,3,4,5,6,7,8,9\}\). Sorted in descending order, they are \(9,8,7,6,5,4,3,2\). For instance, the 3rd largest is \(7\).

This problem was modified by expect2004 on 2020-11-25 and may be one of the final contributions before his retirement.

inputFormat

The input consists of a single line containing two positive integers \(N\) and \(K\) separated by a space.

\(N\) is the parameter in the condition \(a_k^{k} \le N\), and \(K\) denotes that you should output the \(K\)th largest \(N\)-pseudo-smooth number.

outputFormat

Output a single integer, the \(K\)th largest \(N\)-pseudo-smooth number.

sample

10 3

7