#include <bits/stdc++.h>
#include "souvenirs.h"
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
const int N=1e5+5;
int n,cnt[N];
ll cost[N];
void rec(int idx,ll budget){
if(idx>=n||~cost[idx])return;
auto res=transaction(budget-1);
if(res.first.empty())return;
int cur=res.first.front();
for(auto e:res.first)cnt[e]++;
if(res.first.size()>1){
ll rem=budget-1-res.second,per=rem/res.first.size()+1;
for(int i=res.first.size()-1;i>0;i--)(~cost[res.first[i]]?0:(rec(res.first[i],per),0)),res.second+=cost[res.first[i]];
}
cost[cur]=budget-1-res.second,rec(cur+1,cost[cur]);
}
void buy_souvenirs(int N,ll P){
n=N;
for(int i=0;i<n;i++)cost[i]=-1,cnt[i]=0;
cost[0]=P,rec(1,P);
for(int i=0;i<n;i++)while(cnt[i]<i)cnt[i]++,transaction(cost[i]);
}
