#2553. 神奇的四次方数

神奇的四次方数

题目背景

在你的帮助下,v 神终于帮同学找到了最合适的大学,接下来就要通知同学了。在班级里负责联络网的是 dm 同学,于是 v 神便找到了 dm 同学,可 dm 同学正在忙于研究一道有趣的数学题,为了请 dm 出山,v 神只好请你帮忙解决这道题了。

题目描述

将一个整数 mm 分解为 nn 个四次方数的和的形式,要求 nn 最小。例如,当 m=706m=706 时,因为 706=54+34706=5^4+3^4,所以有 n=2n=2。可以证明此时 nn 最小。

输入格式

一行,一个整数 mm

输出格式

一行,一个整数 nn

样例 #1

样例输入 #1

706

样例输出 #1

2

提示

数据范围及约定

  • 对于 30%30\% 的数据,m5000m \le 5000
  • 对于 100%100\% 的数据,m100,000m \le 100,000