#include<bits/stdc++.h> using namespace std; pair<vector<int>,long long> transaction(long long M); int cnt=0; pair<vector<int>,long long>c[105]; long long k[105]; long long p1[105]; int let[105]; void remove(vector<int>v) { for(int i:v) { let[i]--; } } void buy_souvenirs(int N,long long p0) { for(int i=0;i<N;i++) { let[i]=i; } long long last=p0-1; while(true) { //cout<<last<<' '; auto [v,r]=transaction(last); remove(v); c[v.back()]={v,r}; k[v.back()]=last; long long sum=last-r; if(v.size()==1&&v.back()==N-1) { p1[N-1]=sum; break; } if(v.size()==1) { last=sum-1; } else { last=sum/long(v.size())-1; } } //cout<<'\n'; for(int i=N-2;i>=2;i++) { if(c[i].first.empty()) { auto [v,r]=transaction(2*p1[i+1]); remove(v); //cout<<2*p1[i+1]<<' '; p1[i]=2*p1[i+1]-r; for(i=0;i<long(v.size())-1;i++) { p1[i]-=v[i]; } } else { auto [v,r]=c[i]; remove(v); p1[i]=k[i]-r; for(i=0;i<long(v.size())-1;i++) { p1[i]-=v[i]; } } } for(int i=2;i<N;i++) { for(int j=0;j<let[i];j++) { //cout<<p1[i]<<' '; transaction(p1[i]); } } }