#include "souvenirs.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
#define tra transaction
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<vector<int>,ll> pvi;
const int MAXN = 2e5+10;
ll n, c[MAXN], buy[MAXN];
vector<pvi> que;
bool done = 0;
void clean(){
done = 1;
vector<pvi> all;
for(auto [vec, tot] : que){
vector<int> baru;
for(auto in : vec){
if(c[in] == -1) baru.pb(in);
else tot -= c[in];
}
if(baru.size()==1){
c[baru[0]] = tot;
done = 0;
} else {
all.pb(make_pair(baru, tot));
}
}
swap(all, que);
}
ll las, cari;
void op(){
while(true){
auto [aw, sis] = tra(las);
for(auto in : aw) buy[in]++;
vector<int> vec;
for(auto in : aw){
if(c[in] != -1) sis -= c[in];
else vec.pb(in);
}
ll tot = las-sis;
if(vec.size() == 1){
c[vec[0]] = tot;
if(vec[0] == cari) break;
las = tot-1;
} else {
que.pb(pvi(vec, tot));
las = tot/vec.size();
}
}
}
void buy_souvenirs(int N, long long P0) {
n = N;
c[0] = P0;
for(int i=1; i<=n-1; i++) c[i] = -1;
las = c[0]-1; cari = n-1;
op();
while(!done) clean();
while(!que.empty()){
auto [aw, sis] = que.back(); que.pop_back();
for(int i=n-1; i>=1; i--){
if(c[i]==-1){
cari = i; break;
}
}
las = sis/aw.size();
op();
while(!done) clean();
}
// for(int i=1; i<=n-1; i++){
// cerr << c[i] << ' ';
// }
// cerr <<" cost\n";
for(int i=1; i<=n-1; i++){
while(buy[i] < i){
tra(c[i]); buy[i]++;
}
}
return;
}
