P1679 Magical Fourth Power Numbers

With your help, v 神 (v shen) finally found the most suitable university for a classmate, and now it is time to inform them. The classmate in charge of the contact network in the class is dm, so v 神 went to find dm. However, dm was busy studying an interesting math problem. To invite dm to help, v 神 asked you to solve this problem.

Decompose an integer $m$ into a sum of $n$ fourth powers, with $n$ being as small as possible. For example, when $m=706$, since $706=5^4+3^4$, we have $n=2$. It can be proven that in this case $n$ is minimal.

One line, an integer $m$.

One line, an integer $n$.

Constraints - For $30\%$ of the testdata, $m \le 5000$. - For $100\%$ of the testdata, $m \le 100{,}000$. Translated by ChatGPT 5