#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
struct nod {
    int vi;
    int wi;
};
int power[106];
void getpower() {
    for(int i = 0; i < 106; i++) { //求出每个物体的体积
        power[i] = i * i;
    }
}
vector<int> dp(10006, -0xfffffff); // dp数组初始化
int main(void) {
    /*
    将这个问题看作是完全背包问题，也就是给定的数值 n 看作是背包的体积容量，装满背包能获得的最大收益
    完全平方数 power[] 看作是 准备装入背包的物体，每个power都是个物体的，物体的体积就是 i^2自身，装入每个物体的权重收益就是-1的，
    这个权重收益被用来计数，因需要装满背包能获得最大收益，但权重-1<0，也就是收益的绝对值越小越好，也就是物体的个数越少越好，也就符合了题目的最少要求
    */
    int i, j, k, n, m, maxmax, x, y, z, value, num;
    cin>>n;
    getpower();
    value = n;
    num = n;
    dp[0] = 0;
    for(i = 1; i <= sqrt(num); i++) {
        // for(j = value; j >= power[i]; j--) {
/*
j顺序递增的，此时的j-t[i].vi是逆序递增，但是j是顺序递增，又dp[0]=0，所以dp[j]的小值先算出来，小容量背包装了物品t[i].wi，不妨设容量是 jk.
随着j递增的，此时j-t[i].vi是逆序递增，当j-t[i].vi=jk时，或者j-t[i].vi是jk的整数倍时，就可以拿了小容量 t[i].wi放入到背包，相当是这件物品被放了两次，重复了，
j顺序递增可以用来求解 完全背包问题，也就是物品可以重复放多次，也就是物品数量无限。
下面的示例分别是j和j-t[i].vi，若j=2时装入了物品t[0]，那么j=4时，还可以继续装入物品t[0]
j     j-t[i].vi
2        0
3        1
4        2


然后来看正常的0-1背包问题的，j逆序递减的，此时的j-t[i].vi是顺序递减，所以dp[j]的右侧大值先算了出来，大容量背包装了物品，不妨设容量是 jb.
随着j递减的，此时的j-t[i].vi顺序递减的，又初始化的小容量都是0或者-inf，大容量装入小容量还是<0或者=0的，不会出现重复装的问题  
下面的示例分别是j和j-t[i].vi，若j=4时装入了物品t[2]，因dp[2]<=0，所以dp[4]基本不变的，而且后续不会重复装入
j     j-t[i].vi
5        3
4        2
3        1
2        0
*/
        for(j = power[i]; j <=value; j++) {
            if(j-power[i] >=0 ) {
                dp[j] = max(dp[j], dp[j-power[i]] -1);  //收益默认都是-1
            }
        }
    }
    if(dp[value] >= -n) printf("%d", -dp[value]); // 和完全背包问题，稍稍不同的是，需要>-n，而不是>0，因这的收益都是-1<0，所以最后的收益不可能>0，只可能>-n。
    else cout<<0;
    return 0;
}

将这个问题看作是完全背包问题，也就是给定的数值 n 看作是背包的体积容量，装满背包能获得的最大收益

完全平方数 power[] 看作是 准备装入背包的物体，每个power都是个物体的，物体的体积就是 i^2自身，装入每个物体的权重收益就是-1的，

这个权重收益被用来计数，因需要装满背包能获得最大收益，但权重-1<0，也就是收益的绝对值越小越好，也就是物体的个数越少越好，也就符合了题目的最少要求

j顺序递增的，此时的j-t[i].vi是逆序递增，但是j是顺序递增，又dp[0]=0，所以dp[j]的小值先算出来，小容量背包装了物品t[i].wi，不妨设容量是 jk.

随着j递增的，此时j-t[i].vi是逆序递增，当j-t[i].vi=jk时，或者j-t[i].vi是jk的整数倍时，就可以拿了小容量 t[i].wi放入到背包，相当是这件物品被放了两次，重复了，

j顺序递增可以用来求解 完全背包问题，也就是物品可以重复放多次，也就是物品数量无限。

下面的示例分别是j和j-t[i].vi，若j=2时装入了物品t[0]，那么j=4时，还可以继续装入物品t[0]

j j-t[i].vi

2 0

3 1

4 2

然后来看正常的0-1背包问题的，j逆序递减的，此时的j-t[i].vi是顺序递减，所以dp[j]的右侧大值先算了出来，大容量背包装了物品，不妨设容量是 jb.

随着j递减的，此时的j-t[i].vi顺序递减的，又初始化的小容量都是0或者-inf，大容量装入小容量还是<0或者=0的，不会出现重复装的问题

下面的示例分别是j和j-t[i].vi，若j=4时装入了物品t[2]，因dp[2]<=0，所以dp[4]基本不变的，而且后续不会重复装入

j j-t[i].vi

5 3

4 2

3 1

2 0