Hide

Problem AB
Tightly Packed

/problems/tightlypacked/file/statement/en/img-0001.png

Consider packing widgets for shipping where widgets cannot be stacked upon each other (2D packing). Each widget has a $1\times ~ l$ footprint and is $1$ unit high.

Boxes are available in any $W$ by $H$ by $1$ size such that $H/2 \leq W \leq 2H$, with $W$ and $H$ being integers. The company wants to minimize the amount of packing material that will be needed to fill empty squares in a box.

Given $N$, the number of widgets to be shipped, what is the smallest number of squares that will be left empty when those widgets are packed for shipping?

Input

Input consists of one line containing an integer $N$, the number of widgets to be packed, where $1 \leq N \leq 10^{16}$.

Output

Print a single line containing an integer denoting the minimum number of empty squares.

Sample Input 1 Sample Output 1
47
1
Sample Input 2 Sample Output 2
523
2
Sample Input 3 Sample Output 3
10000000000001
6

Please log in to submit a solution to this problem

Log in