3D Printed Statues

Interview

Time limit2sMemory limit512 MB

Summary

With one printer that prints a statue or a new printer each day, find the fewest days to produce at least n statues.

Level: Medium5 of 10
Topics: Greedy, Math, Implementation, Brute force
Solved: No attempts yet

Problem

You own one 3D printer and need to produce $n$ statues with it. Printing the statues one at a time takes a long time, so printing a new printer first can be faster. A newly printed printer can print statues or print yet another printer.

Every print job takes one full day. Each day you decide, for every printer you own, whether it prints a statue or prints a new printer. A printer produced on a given day is usable from the next day on, and a printer is never consumed by a job.

Find the minimum number of days needed to print at least $n$ statues.

Input

The first line contains one integer $n$ , the number of statues you need ( $1 \le n \le 10000$ ).

Output

Print one integer on a single line, the minimum number of days needed to print at least $n$ statues.

Examples2

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
5
```
Expected output
```
4
```