#include<bits/stdc++.h> using namespace std; pair<vector<int>,long long> transaction(long long M); const int MAXN=105; long long p[MAXN]; int n; vector<int>k[MAXN]; long long r[MAXN]; long long s[MAXN]; int let[MAXN]; void clean(int c) { while(k[c].size()&&p[k[c].back()]>0) { r[c]+=p[k[c].back()]; k[c].pop_back(); } } long long sm(int c) { long long sum=s[c]-r[c]; return sum/k[c].size(); } void remove(vector<int>v) { for(int i:v) { let[i]--; } } void solve(int a){ clean(a); while(k[a].size()>1) { long long w=sm(a); auto[v,e]=transaction(w); remove(v); k[v[0]]=v; r[v[0]]=e; s[v[0]]=w; solve(v[0]); clean(a); } p[a]=s[a]-r[a]; if(a!=n-1&&p[a+1]==0) { auto[v,e]=transaction(p[a]-1); remove(v); k[v[0]]=v; r[v[0]]=e; s[v[0]]=p[a]-1; solve(a+1); } } void buy_souvenirs(int N,long long p0) { n=N; for(int i=1;i<N;i++) { let[i]=i; } p[0]=p0; auto[v,e]=transaction(p[0]-1); remove(v); k[1]=v; r[1]=e; s[1]=p[0]-1; solve(1); for(int i=2;i<N;i++) { for(int j=0;j<let[i];j++) { transaction(p[i]); } } }