The Romanian Sieve

Time limit2sMemory limit2048 MB

Summary

Given t, find the largest n such that the sieve's inner loop runs at most t times, where that count is the sum of floor(n/i) for i from 1 to n.

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

Problem

Ionuț Cercel, the son of Petrică Cercel, achieved everything there was to achieve in music after the absolute hit "Made in Romania".

Now he has become interested in competitive programming. While preparing for the training camp in Phapos, he came across a concept called "The Romanian Sieve", which can be summarized by the following code:

    int64_t iters = 0;
    for (int64_t i = 1; i ≤ n; i++) {
        for (int64_t j = i; j ≤ n; j += i) {
            max_div[j] = i;
            iters++;
        }
    }

As a curious person, Ionuț asks himself: "Given an integer $t$ , what is the largest value of $n$ such that iters $\leq t$ after running the Romanian Sieve algorithm?" Please help him answer this question.

Input

The first line contains an integer $t$ ( $1 \leq t \leq 3 \cdot 10^{13}$ ).

Output

Print one integer: the maximum $n$ such that iters $\leq t$ after running the algorithm.

Examples2

Example 1
Input
```
11
```
Expected output
```
5
```
Example 2
Input
```
2846010382
```
Expected output
```
149946143
```