#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
std::pair<std::vector<int>, long long> transaction(long long M);
map<ll,std::pair<std::vector<int>, long long>>dp;
const int MAXN = 301;
ll vis[MAXN], cant[MAXN];
std::pair<std::vector<int>, long long> trans(ll M)
{
auto it=dp.find(M);
if(it==dp.end())
{
dp[M]=transaction(M);
for(auto k:dp[M].fr)
cant[k]++;
return dp[M];
}
return it->se;
}
void calc(ll N, ll P0)
{
std::pair<std::vector<int>, long long> res;
ll x, cost, l, r, piv, pos, sum, i;
auto can = [&](ll a, ll b)
{
sum = 0;
for (i = 0; i < b; i++)
{
sum += a;
a--;
}
return sum >= x;
};
res = trans(P0 - 1);
while(true)
{
x = P0 - res.se - 1;
vector<int> sig;
for (auto k : res.fr)
{
if (vis[k])
x -= vis[k];
else
sig.pb(k);
}
if (sz(sig) == 0)
return;
cost = x;
if (sz(sig) == 1)
{
vis[sig[0]] = cost;
bool seg = 0;
for (i = sig[0]; i < N; i++)
if (vis[i] == 0)
seg = 1;
if (seg)
calc(N, cost);
return;
}
else
{
l = 1, r = cost;
pos = cost;
while (l <= r)
{
piv = (l + r) / 2;
if (can(piv, sz(sig)))
{
pos = piv;
r = piv - 1;
}
else
l = piv + 1;
}
calc(N,pos);
}
}
}
void buy_souvenirs(int N, long long P0)
{
vis[0] = P0;
calc(N, P0);
bool band=0;
ll i;
while(true)
{
band=0;
for(i=N-1; i>=0; i--)
{
if(vis[i]==0)
band=1;
else if(band)
break;
}
if(!band)
break;
calc(N,vis[i]);
}
for (ll i = 1; i < N; i++)
{
while (cant[i] < i)
{
transaction(vis[i]);
cant[i]++;
}
}
return;
}
