#include "bits/stdc++.h" using namespace std; #define int long long #define FOR(i, a, b) for(int i=(a);i<(b);i++) #define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--) #define REP(i, n) for(int i=0; i<(n); i++) #define RREP(i, n) for(int i=(n-1); i>=0; i--) #define ALL(a) (a).begin(),(a).end() #define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end()); #define CONTAIN(a, b) find(ALL(a), (b)) != (a).end() #define array2(type, x, y) array<array<type, y>, x> #define vector2(type) vector<vector<type> > #define out(...) printf(__VA_ARGS__) int dxy[] = {0, 1, 0, -1, 0}; void solve(); signed main() { #if DEBUG std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf()); #endif cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; } /*================================*/ int N,M,Q; int ans; int MAX = 1e7; vector<int> S; // 1枚で払える金額一覧 vector<int> D; // 2枚で払える金額一覧 vector<int> C(2e7, INT_MAX); // SorDに入っている金額のチェック用 int check(int n) { int ret = INT_MAX; for (int m:S) { ret = min(ret,1 + C[n-m]); } for (int m:D) { ret = min(ret,2 + C[n-m]); } return ret; } void solve() { cin>>N; REP(i,sqrt(N)+2) { int n = i * (i+1) / 2; if (n > MAX) break; S.push_back(n); C[n] = 1; } for (int a:S) for (int b:S) { int n = a + b; if (n > MAX) break; if (C[n]==1) continue; D.push_back(n); C[n] = 2; } cout << check(N) << endl; }