题目描述

小禾正在参加海曙区“呦呦海贝”活动中的航海闯关游戏。出发前，他需要为小船准备恰好 $n$ 枚虚拟海贝。

游戏里的补给站可以帮助他收集海贝，但需要消耗能量。整个补给过程从 $0$ 枚海贝开始，必须按下面三个阶段依次进行：

1. 基础补给：领取 $a$ 枚海贝，每枚消耗 $1$ 单位能量。
2. 连续翻倍：使用翻倍功能 $b$ 次。每使用一次，已有的海贝数量就变成原来的 $2$ 倍，消耗 $1$ 单位能量。
3. 最后补充：再领取 $c$ 枚海贝，每枚消耗 $1$ 单位能量。此后不能再使用翻倍功能。

其中 $a,b,c$ 都是非负整数，任意阶段都可以跳过。

补给完成后，小禾共有 $a\times2^b+c$ 枚海贝，总共消耗 $a+b+c$ 单位能量。

请你计算，让海贝数量恰好等于 $n$，最少需要消耗多少单位能量。

输入格式

输入一行，包含一个正整数 $n$，表示需要的虚拟海贝数量。

输出格式

输出一行，包含一个整数，表示最少需要消耗的能量。

100

12

1

1

说明/提示

样例 $1$ 中，可以先领取 $3$ 枚虚拟海贝，连续翻倍 $5$ 次，再领取 $4$ 枚虚拟海贝。

最终共有 $3\times2^5+4=100$ 枚虚拟海贝，消耗 $3+5+4=12$ 单位能量。可以证明，没有能量消耗更少的方案。

样例 $2$ 中，直接领取 $1$ 枚虚拟海贝即可。

对于 $100\%$ 的数据，$1\le n\le10^9$。