問題文

YUKI国の通貨の単位は円と呼ばれ、額面が三角数であるような硬貨が流通しています。
すなわち、任意の正整数 $k$ に対して、$k\times (k+1)÷2$ 円の硬貨が流通しています。
流通している硬貨を額面を小さい方からいくつか列挙すると、$1,3,6,10,15,21,28,\dots$ 円です。

雪男くんは、全ての額面の硬貨を ${10}^{100}$ 枚持っており、$N$ 円の品物を購入しようと思っています。
その際、YUKI国の硬貨でちょうど $N$ 円となるように支払いを行います。

雪男くんは、支払いに使用する硬貨の枚数を最小化したいです。
支払いに使用する硬貨の枚数の最小値を求めてください。

入力

N

$1\le N\le {10}^7$
$N$ は整数

出力

答えを1行で出力してください。最後に改行してください。

サンプル

8

3

10

1

15415

2