OpenKattis
Kattis Set 11

#### Start

2020-03-30 05:15 AKDT

## Kattis Set 11

#### End

2020-04-06 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -241 days 0:19:04

164:15:00

0:00:00

# Problem LTightly Packed

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