D - 2-variable Function Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数 N が与えられるので、以下の条件を全て満たす最小の整数 X を求めてください。

  • X は N 以上である。
  • 非負整数 (a,b) の組であって、 X=a^3+a^2b+ab^2+b^3 を満たすようなものが存在する。

制約

  • N は整数
  • 0 \le N \le 10^{18}

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを整数として出力せよ。

入力例 1

9

出力例 1

15

9 \le X \le 14 であるようなどの整数 X についても、問題文中の条件を満たすような (a,b) は存在しません。
X=15 は (a,b)=(2,1) とすると問題文中の条件を満たします。

入力例 2

0

出力例 2

0

N 自身が条件を満たすこともあります。

入力例 3

999999999989449206

出力例 3

1000000000000000000

入出力が 32bit 整数型に収まらない場合があります。

Score : 400 points

Problem Statement

Given an integer N, find the smallest integer X that satisfies all of the conditions below.

  • X is greater than or equal to N.
  • There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.

Constraints

  • N is an integer.
  • 0 \le N \le 10^{18}

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer as an integer.

Sample Input 1

9

Sample Output 1

15

For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.

Sample Input 2

0

Sample Output 2

0

N itself may satisfy the condition.

Sample Input 3

999999999989449206

Sample Output 3

1000000000000000000

Input and output may not fit into a 32-bit integer type.