P3583 [POI 2015 R1] Sum of Squares

Consider expressing a positive integer $n$ as a sum of several distinct squares. For example, $30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2$, while $8$ has no such decomposition. Let $k(n)$ denote the minimal possible value of the largest base among all such decompositions of $n$. If no such decomposition exists, set $k(n) = \infty$. For example: $k(1) = 1$, $k(8) = \infty$, $k(378) = 12$, $k(380) = 10$. A number $x$ is called "overweight" if and only if there exists $y > x$ such that $k(y) < k(x)$. From the examples above, $378$ is an "overweight" number. Given $n$, you need to: 1. Compute $k(n)$. 2. Count how many "overweight" numbers are in the range from $1$ to $n$.

The input contains a single line with a positive integer $n$.

Output one line containing two integers, which are the answers to the two questions above. If $k(n) = \infty$, output a minus sign `-` instead.

Constraints For 100 % of the testdata, $1 \le n \le 10^{18}$. Original title: Kwadraty. Translated by ChatGPT 5