Candies

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

After passing a test, Vasya got himself a box of $\mathrm{nn candies.\; He\; decided\; to\; eat\; an\; equal\; amount\; of\; candies\; each\; morning\; until\; there\; are\; no\; more\; candies.\; However,\; Petya\; also\; noticed\; the\; box\; and\; decided\; to\; get\; some\; candies\; for\; himself.}$

This means the process of eating candies is the following: in the beginning Vasya chooses a single integer $\mathrm{kk,\; same\; for\; all\; days.\; After\; that,\; in\; the\; morning\; he\; eats kk candies\; from\; the\; box\; (if\; there\; are\; less\; than kk candies\; in\; the\; box,\; he\; eats\; them\; all),\; then\; in\; the\; evening\; Petya\; eats 10\%10\% of\; the\; candies remaining in\; the\; box.\; If\; there\; are\; still\; candies\; left\; in\; the\; box,\; the\; process\; repeats —\; next\; day\; Vasya\; eats kk candies\; again,\; and\; Petya — 10\%10\% of\; the\; candies\; left\; in\; a\; box,\; and\; so\; on.}$

If the amount of candies in the box is not divisible by $\mathrm{1010,\; Petya\; rounds\; the\; amount\; he\; takes\; from\; the\; box\; down.\; For\; example,\; if\; there\; were 9797 candies\; in\; the\; box,\; Petya\; would\; eat\; only 99 of\; them.\; In\; particular,\; if\; there\; are\; less\; than 1010 candies\; in\; a\; box,\; Petya\; won\text{'}t\; eat\; any\; at\; all.}$

Your task is to find out the minimal amount of $\mathrm{kk that\; can\; be\; chosen\; by\; Vasya\; so\; that\; he\; would\; eat\; at\; least\; half\; of\; the nn candies\; he\; initially\; got.\; Note\; that\; the\; number kk must\; be\; integer.}$

Input

The first line contains a single integer $\mathrm{nn (1\le n\le 10181\le n\le 1018) —\; the\; initial\; amount\; of\; candies\; in\; the\; box.}$

Output

Output a single integer — the minimal amount of $\mathrm{kk that\; would\; allow\; Vasya\; to\; eat\; at\; least\; half\; of\; candies\; he\; got.}$

Example

input

Copy

68

output

Copy

3

Note

In the sample, the amount of candies, with $\mathrm{k=3k=3,\; would\; change\; in\; the\; following\; way\; (Vasya\; eats\; first):}$

$\mathrm{68\to 65\to 59\to 56\to 51\to 48\to 44\to 41\to 37\to 34\to 31\to 28\to 26\to 23\to 21\to 18\to 17\to 14\to 13\to 10\to 9\to 6\to 6\to 3\to 3\to 068\to 65\to 59\to 56\to 51\to 48\to 44\to 41\to 37\to 34\to 31\to 28\to 26\to 23\to 21\to 18\to 17\to 14\to 13\to 10\to 9\to 6\to 6\to 3\to 3\to 0.}$

In total, Vasya would eat $\mathrm{3939 candies,\; while\; Petya — 2929.}$

 

#include