#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;
// got cheapest
if(gotten1.size() == 1){
use = (expless1) - change1 - 1;
auto [gotten2, change2] = transaction(use);
auto [gotten3, change3] = transaction(use);
}
// bough 2 items
else{
use = (expless1 - change1 - 1) / 2;
auto [gotten2, change2] = transaction(use);
}
return;
}
vector<ll> prices(N);
vector<int> bought(N, 0);
prices[0] = P0;
for (int i = 1; i < N; ++i) {
auto [gotten, change] = transaction(prices[i - 1] - 1);
for (auto item : gotten)
bought[item]++;
prices[i] = prices[i - 1] - (gotten.size() == 1 ? 1 + change : 2);
}
for (int i = 1; i < N; ++i) {
while (bought[i] < i) {
auto [gotten, change] = transaction(prices[i]);
for (int item : gotten)
bought[item]++;
}
}
}
