Overweighted Number and Minimal Largest Square Sum

Given a positive integer \(n\), consider splitting \(n\) into the sum of several distinct square numbers. For instance:

• \(30 = 1^2 + 2^2 + 5^2 = 1^2 + 2^2 + 3^2 + 4^2\)
• \(8\) cannot be expressed in such a way.

Define \(k(n)\) as the minimum possible value of the largest base among all valid representations of \(n\) as a sum of distinct squares. If no valid representation exists then we define \(k(n)=\infty\). For example:

• \(k(1)=1\)
• \(k(8)=\infty\)
• \(k(378)=12\)
• \(k(380)=10\)

A number \(x\) is called overweighted if and only if there exists a \(y > x\) such that \(k(y) < k(x)\). For example, from the data above, \(378\) is overweighted.

Your task is, given \(n\), to:

1. Compute \(k(n)\). (If \(k(n)=\infty\), output -1.)
2. Count how many numbers in the range \([1, n]\) are overweighted.

inputFormat

The input consists of a single positive integer \(n\) (\(1 \le n \le \text{some reasonable limit}\)).

outputFormat

Output two numbers separated by a space: the first is \(k(n)\) (print -1 if \(k(n)=\infty\)) and the second is the number of overweighted numbers in the range \([1, n]\).

sample

1

1 0