#include "souvenirs.h"
#include <bits/stdc++.h>
using namespace std;
static pair<int,long long> sim(const vector<int>& P, long long M){
long long r=M;
int mask=0;
for(int i=0;i<(int)P.size();i++){
if(r>=P[i]){
r-=P[i];
mask|=(1<<i);
}
}
return {mask,r};
}
void buy_souvenirs(int N, long long P0){
vector<vector<int>> cand;
vector<int> vals;
for(int x=1;x<=10;x++) if(x<P0) vals.push_back(x);
vector<int> cur(N);
cur[0]=(int)P0;
function<void(int,int,int,vector<int>&)> dfs = [&](int idx,int last,int need,vector<int>& pick){
if((int)pick.size()==need){
vector<int> P(N);
P[0]=(int)P0;
for(int i=1;i<N;i++) P[i]=pick[i-1];
cand.push_back(P);
return;
}
for(int v=last-1;v>=1;v--){
bool ok=true;
for(int x:pick) if(x==v) ok=false;
if(!ok) continue;
if(v>=P0) continue;
pick.push_back(v);
dfs(idx+1,v,need,pick);
pick.pop_back();
}
};
if(N==1) return;
vector<int> pick;
dfs(1,(int)P0,N-1,pick);
auto bestM = [&](int lb)->long long{
long long best=-1;
int bestWorst=INT_MAX;
for(int m=lb;m<=P0-1;m++){
unordered_map<long long,int> cnt;
cnt.reserve(cand.size()*2+7);
for(auto &P:cand){
auto s=sim(P,m);
long long key=((long long)s.first<<20) ^ (s.second&((1LL<<20)-1));
cnt[key]++;
}
int worst=0;
for(auto &kv:cnt) worst=max(worst,kv.second);
if(worst<bestWorst){
bestWorst=worst;
best=m;
}
}
if(best==-1) best=lb;
return best;
};
while(cand.size()>1){
int lb=1;
for(auto &P:cand) lb=max(lb,P.back());
long long m=bestM(lb);
auto real=transaction(m);
int mask=0;
for(int t:real.first) mask|=(1<<t);
long long rem=real.second;
vector<vector<int>> nxt;
nxt.reserve(cand.size());
for(auto &P:cand){
auto s=sim(P,m);
if(s.first==mask && s.second==rem) nxt.push_back(P);
}
cand.swap(nxt);
}
vector<int> P=cand[0];
for(int i=1;i<N;i++){
for(int t=0;t<i;t++){
transaction(P[i]);
}
}
}
