Squares

We call a decomposition of a positive integer any way to write it as a sum of distinct squares of positive integers. For example, 30 has two decompositions: $30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2$. The number 8 has none.

Let $k(n)$ be the minimum, over all decompositions of $n$, of the largest integer whose square appears in the decomposition. If $n$ has no decomposition, then $k(n) = \infty$. For example, $k(1) = 1$, $k(8) = \infty$, $k(30) = 4$, $k(378) = 12$, and $k(380) = 10$.

An integer $x$ is overgrown if there is an integer $y > x$ with $k(y) < k(x)$. In the example above, 378 is overgrown.

For a given $n$, find $k(n)$ and the number of overgrown integers from 1 to $n$, inclusive.

The first and only line contains a single integer $n$ ($1 \le n \le 10^{18}$). Tests worth 45% of the score satisfy $n \le 50\,000\,000$. A subset worth 30% satisfies $n \le 1\,000\,000$, and a smaller subset worth 20% satisfies $n \le 1000$.

Print two integers separated by a single space: first $k(n)$, then the number of overgrown integers from 1 to $n$. If $k(n) = \infty$, print a minus sign (-) instead of the first number.