#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(),x.end()
using ll = long long;
#define pi pair<int,int>
#define f first
#define s second
const int len = 1.3e7 + 5;
int sum[len], ls[len], rs[len], l[len], r[len], cnt = 0;
int build(int li, int ri)
{
int vr = cnt++;
l[vr] = li, r[vr] = ri, sum[vr] = 0;
if (li != ri) ls[vr] = build(li, (li + ri) / 2), rs[vr] = build((li + ri) / 2 + 1, ri);
return vr;
}
int upd(int i, int vr) // vrati novy koren
{
if (i < l[vr] || i > r[vr]) return vr;
int v2 = cnt++;
sum[v2] = sum[vr] + 1;
l[v2] = l[vr], r[v2] = r[vr];
if (l[vr] != r[vr]) ls[v2] = upd(i, ls[vr]), rs[v2] = upd(i, rs[vr]);
return v2;
}
int query(int li, int ri, int vr)
{
if (ri < l[vr] || li > r[vr]) return 0;
if (li <= l[vr] && r[vr] <= ri) return sum[vr];
return query(li, ri, ls[vr]) + query(li, ri, rs[vr]);
}
int st[(int)5e5+5];
pi a[(int)5e5];
int n;
void init(int _n, int f[], int s[]) {
n=_n;
forn(i,n) a[i]={f[i],s[i]};
vector<vector<int>> v(n+1);
forn(i,n) v[a[i].s].pb(i);
st[n+1]=build(0,n);
for(int i=n; i>0; --i) {
st[i]=st[i+1];
for(auto&x:v[i]) {
st[i]=upd(a[x].f,st[i]);
}
}
}
int can(int m, int k[]) {
vector<int> v(m);
forn(i,m) v[i]=k[i];
sort(all(v));
int s=0; forn(i,m) s+=k[i];
if (s>n) return 0;
vector<pi> z;
forn(i,m) {
if (!z.size()) {
z.pb({v[i],1}); continue;
}
if (v[i]==z.back().f) z.back().s++;
else z.pb({v[i],1});
}
int t=z.size();
vector<int> dp(t+1,-1e9);
dp[0]=0;
forn(i,t) {
forn(j,i+1) {
int cnt;
if (j==0) {
cnt=query(0,z[i].f,st[z[i].f]);
} else {
cnt=query(z[j-1].f+1,z[i].f,st[z[i].f]);
}
dp[i+1]=max(dp[i+1],dp[j]+z[i].f*z[i].s-cnt);
}
if (dp[i+1]>0) return 0;
}
return 1;
}
