#include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vector<int>vint; typedef pair<int,int>pint; typedef vector<pint>vpint; template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;} template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;} int dp[111111]; int N; signed main(){ vint v; for(int i=1;i*(i+1)/2<=10000000;i++)v.pb(i*(i+1)/2); dp[0]=0; for(int i=1;i<111111;i++){ dp[i]=INT_MAX; for(int j=0;v[j]<=i;j++){ chmin(dp[i],dp[i-v[j]]+1); } } cin>>N; if(find(all(v),N)!=v.end()){ cout<<1<<endl; return 0; } int ans=INT_MAX; rep(i,v.size())rep(j,v.size()){ int n=N-v[i]-v[j]; if(n<0)continue; if(n>=111111)continue; chmin(ans,dp[n]+2); } cout<<ans<<endl; return 0; }