该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：coin.in 输出文件：coin.out

A 国的货币单位称为元，市面上流通的硬币面额均为三角数。具体来说，对于任意正整数 $k$，面额为 $k \times (k+1) \div 2$ 元的硬币均在流通。若将流通的硬币按面额从小到大列举，依次为 $1, 3, 6, 10, 15, 21, 28, \dots$ 元。

小明打算购买一件价格为 $N$ 元的商品，并用 A 国的硬币恰好支付 $N$ 元。他拥有每种面额的硬币各 $10^{100}$ 枚。小明希望尽可能减少支付时使用的硬币总枚数。

请你求出支付时所需硬币枚数的最小值。

输入格式

一个正整数 $N$。

输出格式

一个整数，表示支付时所需硬币枚数的最小值。

样例

样例 1

8

3

样例 2

10

1

样例 3

15415

2

数据范围

对于 20% 的数据，$N \le 100$。

对于 60% 的数据，$N \le 10000$。

对于 100% 的数据，$1 \le N \le 10^7$。