#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a>n; using P = pair; vector

vp; for(Int i=1;i*i<=n;i++) vp.emplace_back(i*i,i); const Int INF = 1e15; vector dp(n+1,INF); dp[0]=0; for(auto p:vp) for(Int i=0;i+p.first<=n;i++) chmin(dp[i+p.first],dp[i]+p.second); Int val=n,state=0; while(val){ //cout<