#include <bits/stdc++.h>
using namespace std;
pair<vector<int>, long long> transaction(long long M);
void buy_souvenirs(int N, long long P0) {
int vars = N - 1;
vector<vector<long long>> A;
vector<long long> B;
vector<long long> got(N, 0);
long long step = max(1LL, P0 / (2 * N + 5));
long long M = P0 - 1;
while ((int)A.size() < vars && M >= 0) {
auto res = transaction(M);
auto &L = res.first;
long long R = res.second;
vector<long long> row(vars, 0);
for (int t : L) {
got[t]++;
if (t > 0)
row[t - 1] = 1;
}
long long paid = M - R;
A.push_back(row);
B.push_back(paid);
M -= step;
}
int eq = A.size();
vector<long long> P(vars, 0);
int r = 0;
for (int c = 0; c < vars && r < eq; ++c) {
int piv = -1;
for (int i = r; i < eq; ++i) {
if (A[i][c] != 0) {
piv = i;
break;
}
}
if (piv == -1) continue;
swap(A[r], A[piv]);
swap(B[r], B[piv]);
for (int i = 0; i < eq; ++i) {
if (i == r) continue;
if (A[i][c] == 0) continue;
long long factor = A[i][c];
for (int j = c; j < vars; ++j)
A[i][j] -= factor * A[r][j];
B[i] -= factor * B[r];
}
r++;
}
for (int i = vars - 1; i >= 0; --i) {
int pivot_col = -1;
for (int j = 0; j < vars; ++j)
if (A[i][j] != 0) {
pivot_col = j;
break;
}
if (pivot_col == -1) continue;
long long sum = B[i];
for (int j = pivot_col + 1; j < vars; ++j)
sum -= A[i][j] * P[j];
P[pivot_col] = sum / A[i][pivot_col];
}
for (int i = 1; i < N; ++i) {
long long need = i - got[i];
while (need > 0) {
transaction(P[i - 1]);
need--;
}
}
}
