通过测试后,Vasya 给自己买了一盒 $$$n$$$ 糖果。他决定每天早上吃等量的糖果,直到吃完为止。然而,佩蒂亚也注意到了这个盒子,并决定给自己买一些糖果。
这意味着吃糖果的过程如下:一开始 Vasya 选择一个整数 $$$k$$$,所有天都相同。之后,早上他会从盒子里吃掉$$$k$$$糖果(如果盒子里的糖果少于$$$k$$$,他就会把它们全部吃掉),然后晚上Petya会吃掉盒子里剩余糖果的$$$10\%$$$。如果盒子里还剩下糖果,这个过程就会重复——第二天 Vasya 会再次吃掉 $$$k$$$ 糖果,而 Petya 会吃掉盒子里剩下的 $$$10\%$$$ 糖果,以此类推。
如果盒子里的糖果数量不能被 $$$10$$$ 整除,Petya 会将他从盒子里拿走的糖果数量向下舍入。例如,如果盒子里有 $$$97$$$ 糖果,Petya 只会吃掉 $$$9$$$ 的糖果。特别是,如果盒子里的糖果少于 $$$10$$$,Petya 根本不会吃任何东西。
你的任务是找出 Vasya 可以选择的 $$$k$$$ 的最小数量,以便他能吃掉他最初得到的 $$$n$$$ 糖果的至少一半。请注意,数字 $$$k$$$ 必须是整数。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — 盒子中糖果的初始数量。
输出
输出一个整数——$$$k$$$ 的最小数量,可以让 Vasya 吃掉他得到的至少一半的糖果。
示例
输入 #1
68
输出 #1
3
注意
在示例中,$$$k=3$$$ 的糖果数量将按以下方式变化(Vasya 先吃):
$$$68 \至65 \至59 \至56 \至51 \至48 \至44 \至41 \\ \至37 \至34 \至31 \至28 \至26 \至23 \至21 \至18 \至17 \至14 \\ \至13 \至10 \至9 \到 6 \到 6 \到 3 \到 3 \到 0$$$。
Vasya 总共会吃 $$$39$$$ 糖果,而 Petya — $$$29$$$。