ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4682: 迈克和巧克力小偷

内存限制：256 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：3 通过：3
提交提交记录统计Web Board

题目描述

迈克的村子传来了坏消息，一些小偷从当地工厂偷了一堆巧克力！可怕！
除了喜欢甜食外，该地区的小偷也非常贪婪。因此，在小偷将他的巧克力数量据为己有之后，下一个小偷将比前一个小偷多拿走k倍。k（k>1） 的值是一个只有他们知道的秘密整数。众所周知，每个小偷的包最多可以携带n个巧克力（如果他们打算拿更多，交易将被取消），并且正好有四个小偷参与其中。
可悲的是，只有盗贼知道 n 的值，但有传言说他们本可以拿走巧克力的方式（对于固定的n，但不是固定的 k）的次数是m。如果其中一个小偷（他们应该按照他们拿巧克力的顺序编号）拿走了不同数量的巧克力，则两种方式被认为是不同的。
迈克想追踪盗贼，所以他想知道他们的包是什么，n的价值将在这方面帮助他。请找到n的最小可能值或告诉他谣言是假的，没有这样的n。

Bad news came to Mike's village, some thieves stole a bunch of chocolates from the local factory! Horrible!
Aside from loving sweet things, thieves from this area are known to be very greedy. So after a thief takes his number of chocolates for himself, the next thief will take exactly k times more than the previous one. The value of k (k>1) is a secret integer known only to them. It is also known that each thief's bag can carry at most n chocolates (if they intend to take more, the deal is cancelled) and that there were exactly four thieves involved.
Sadly, only the thieves know the value of n, but rumours say that the numbers of ways they could have taken the chocolates (for a fixed n, but not fixed k) is m. Two ways are considered different if one of the thieves (they should be numbered in the order they take chocolates) took different number of chocolates in them.
Mike want to track the thieves down, so he wants to know what their bags are and value of n will help him in that. Please find the smallest possible value of n or tell him that the rumors are false and there is no such n.
Input
The single line of input contains the integer m (1≤m≤1015)− the number of ways the thieves might steal the chocolates, as rumours say.
Output
Print the only integer n− the maximum amount of chocolates that thieves' bags can carry. If there are more than one n satisfying the rumors, print the smallest one.
If there is no such n for a false-rumoured m, print -1.
Examples
Input 
1
Output 
8
Input 
8
Output 
54
Input 
10
Output 
-1
Note
In the first sample case the smallest n that leads to exactly one way of stealing chocolates is n=8, whereas the amounts of stealed chocolates are (1,2,4,8) (the number of chocolates stolen by each of the thieves).
In the second sample case the smallest n that leads to exactly 8 ways is n=54 with the possibilities: (1,2,4,8), (1,3,9,27), (2,4,8,16), (2,6,18,54), (3,6,12,24), (4,8,16,32), (5,10,20,40), (6,12,24,48).
There is no n leading to exactly 10 ways of stealing chocolates in the third sample case.

输入格式

单行输入包含整数m （1≤米≤1015)- 正如谣言所说，小偷可能偷走巧克力的方式多种多样。

输出格式

打印唯一的整数n− 盗贼袋可以携带的最大巧克力数量。如果有多个n满足谣言，请打印最小的一个。
如果假传闻的 m 没有这样的n，则 print-1。

Examples
Input 
1
Output 
8
Input 
8
Output 
54
Input 
10
Output 
-1

注意

在第一个样本案例中，导致一种偷巧克力方式的最小n是n=8，而偷巧克力的数量是（1，2，4，8）（每个小偷偷的巧克力数量）。
在第二个样本案例中，导致正好8种方式的最小n是n=54，具有以下可能性：（1，2，4，8）、（1，3，9，27）、（2，4，8，16）、（2，6，18，54）、（3，6，12，24）、（4，8，16，32）、（5，10，20，40）、（6，12，24，48）。
在第三个样本案例中，没有n导致正好10种偷巧克力的方法。



输入样例 复制 

1

输出样例 复制 

8

分类标签