CF333A Secrets

Gerald 一直在偷偷出售国家机密。所有机密的售价均为 $n$ 马克。Gerald 所出售机密的那个国家没有纸币，只有硬币，并且只有面额为三的幂的所有正整数面值的硬币：1 马克、3 马克、9 马克、27 马克等。没有其他面额的硬币。当然，Gerald 希望买家都能正好付清，不用找零。而且所有买家都很尊重他，如果可能的话都会尝试正好付清。 但并不总是都这么顺利。 有一天，一位倒霉的买家来了。他无法凑出正好的金额。于是他拿出自己所有的硬币，尝试用尽量少的硬币给 Gerald 支付一个超过所需金额的数。那么 Gerald 最多可能收到多少枚硬币？ 上一段的正式表述：我们考虑所有无法用硬币正好支付 $n$ 马克的组合。对于每种情况，计算买家至少要用多少枚硬币才能支付不少于 $n$ 马克。在所有这些情况中，求出最小硬币数的最大值。这个值就是我们所要求的答案。

一行一个整数 $n$（$1 \leq n \leq 10^{17}$）。 请不要在 C++ 中使用 %lld 读写 64 位整数。建议使用 cin、cout 流或 %I64d。

输出一行一个整数：倒霉买家支付时 Gerald 最多可能收到的硬币数。

在第一个测试样例中，如果买家只有一枚面值不小于 3 马克的硬币，那么想要支付 1 马克时，他不得不用掉这枚硬币。在本样例中，买家不能有面值为 1 马克的硬币，否则他就可以正好付清。 在第二个测试样例中，如果买家正好有三枚 3 马克的硬币，为了支付 4 马克，他必须用掉其中两枚硬币。买家不会给出三枚硬币，因为他希望支付的硬币数量尽量少。 由 ChatGPT 5 翻译