OIG II - cia

// https://szkopul.edu.pl/problemset/problem/JcJfB1VlW4cFdrCI6yDcQig0/site/?key=statement
// Zadanie Ciąg

#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define int long long
// #define GARY_DBG

constexpr int sizik = 50 * 1001;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef vec<vec<int>> _kra;

std::vector<int> a;
int ost[sizik];

void solve() {
    int n;
    std::cin >> n;

    a.push_back(1);
    a.push_back(2);
    a.push_back(2);
    int curr = 2, idx = 3;
    while ((int)a.size() < 30000) {
        for (int i = 0; i < a[curr]; i++) {
            a.push_back(idx);
        }
        curr++, idx++;
    }

    for (int i = 0; i < (int)a.size(); i++) {
        ost[i + 1] = ost[i] + a[i];
    }

    idx = 1;
    int wynik = 0, prev_znane = 0, prev_wynik = 0;
    uint64_t znane = 0;
    while (znane < n) {
        prev_znane = znane;
        prev_wynik = wynik;
        znane += idx * ((((ost[idx] + 1) * ost[idx]) - (ost[idx - 1] * (ost[idx - 1] + 1))) >> 1);
        wynik += idx * a[idx - 1];
        idx++;
    }
    idx--;

    int c = ost[idx - 1] + 1, c1 = 0;
    while (prev_znane < n) {
        prev_znane += c;
        c1++;
        if (c1 == idx) {
            c1 = 0, c++;
        }
        prev_wynik++;
    }

    std::cout << prev_wynik << '\n';
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}