#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
extern pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
long long expless1 = P0 - 1;
if (N == 2) {
auto [gotten, change] = transaction(expless1);
return;
}
if(N == 3){
auto [gotten1, change1] = transaction(expless1);
ll use;
if(gotten1.size() == 1){
use = (expless1) - change1 - 1;
auto [gotten2, change2] = transaction(use);
auto [gotten3, change3] = transaction(use);
}
else{
use = (expless1 - change1 - 1) / 2;
auto [gotten2, change2] = transaction(use);
}
return;
}
vector<ll> prices(N, -1);
prices[0] = P0;
vector<int> bought(N, 0);
set<int> need;
for (int i = 1; i < N; ++i)
need.insert(i);
while (!need.empty()) {
bool done = false;
for (int idx : need) {
ll low = 1, high = P0 - 1;
while (low <= high) {
ll mid = (low + high) / 2;
auto [gotten, change] = transaction(mid);
ll sum = mid - change;
for (int g : gotten)
bought[g]++;
if (gotten.size() == 1 && gotten[0] == idx) {
prices[idx] = sum;
need.erase(idx);
done = true;
break;
}
if (bought[idx] >= idx) {
need.erase(idx);
done = true;
break;
}
if (find(gotten.begin(), gotten.end(), idx) == gotten.end()) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (done)
break;
}
if (!done)
break;
}
for (int i = 1; i < N; ++i) {
while (bought[i] < i) {
auto [gotten, change] = transaction(prices[i]);
for (int item : gotten)
bought[item]++;
}
}
}
