#include "souvenirs.h"
#include <utility>
#include <vector>
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
#define re exit (0);
#define maxn 1009
typedef pair<vector<int>,ll> Data ;
int cnt_buy [maxn] ;
ll p [maxn] ;
void buy_souvenirs(int N, long long P0) {
Data temp ;
map <ll,Data> answer ;
for ( int i = 0 ; i < N ; i ++ ) p [i] = -1 ;
p [0] = P0 ;
priority_queue<ll,vector<ll>,greater<ll>> S ;
S . push (P0-1) ;
while (!S.empty())
{
ll t = S.top() ; S.pop() ;
if ( !answer.count(t) )
{
answer [t] = transaction (t) ;
for ( auto x : answer [t].fi ) cnt_buy [x] ++ ;
}
ll sum = t - answer [t].se ;
int cnt = answer [t].fi.size () ;
for ( auto x : answer [t].fi )
{
if ( p [x] != - 1 ) sum -= p [x] , cnt -- ;
}
if ( cnt == 1 )
{
for ( auto x : answer [t].fi )
{
if ( p [x] == - 1 )
{
p [x] = sum ;
if ( x + 1 < N && p [x+1] == -1 ) S . push (p[x]-1) ;
}
}
}
else
{
S . push (t) ;
S . push (sum/cnt) ;
}
}
for ( int i = 1 ; i < N ; i ++ )
{
while ( cnt_buy [i] < i ) temp = transaction (p[i]) , cnt_buy [i] ++ ;
}
return ;
}
