AtCoder Beginner Contest 040

B - □□□□□


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君は大きさ 1 メートル四方のタイルを n 枚持っています。

高橋君はこれらのタイルのうちいくつかを、重ならないように隙間なく並べて大きな長方形を作ろうとしています。

出来上がる長方形はできるだけ正方形に近いほうがよいですが、同時に、使わずに余るタイルの枚数ができるだけ少なくなるようにしたいと考えています。

長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和を最小でいくつにできるでしょうか。

制約

  • 1 ≦ n ≦ 100,000

入力

入力は以下の形式で標準入力から与えられる。

n

出力

求めた最小値を 1 行に出力せよ。


入力例1

26

出力例1

1

5 \times 5 の正方形になるように並べると、縦横の長さの差が 0 で、余るタイルの枚数が 1 となり、その和は 1 です。

26 枚のタイルを余らせることなく使い正方形を作ることはできないので、答えは 1 となります。


入力例2

41

出力例2

4

この場合、5 \times 8 の長方形を作ってタイルを 1 枚余らせるのが最適です。


入力例3

100000

出力例3

37

Submit提出する