#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include "teams.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 5e5 + 10;
const int maxq = 2e5 + 10;
pii v[maxn];
int n;
struct node {
node *l, *r;
int v;
node () {
l = r = nullptr;
v = 0;
}
};
inline int val(node *t) {
if (t != nullptr) return t->v;
return 0;
}
inline node* l(node* t) {
return t ? t->l : nullptr;
}
inline node* r(node *t ) {
return t ? t->r : nullptr;
}
inline int valor(node *t) {
return t ? t->v : 0;
}
void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
if (ini == fim) {
no->v = valor(old) + v;
return;
}
int meio = (ini + fim) >> 1;
if (p <= meio) {
if (old == nullptr || old->l == nullptr) no->l = new node;
else no->l = new node(*old->l);
if(old != nullptr && old->r != nullptr) no->r = old->r;
update(l(old), no->l, p, v, ini, meio);
}else {
if (old == nullptr || old->r == nullptr) no->r = new node;
else no->r = new node(*old->r);
if(old != nullptr && old->l != nullptr) no->l = old->l;
update(r(old), no->r, p, v, meio+1, fim);
}
no->v = val(no->l) + val(no->r);
}
int query(node *no, int l, int r, int ini=1, int fim=n) {
if(no == nullptr || ini > r || fim < l) return 0;
l = max(l, ini);
r = min(r, fim);
if(l <= ini && fim <= r) return no->v;
int meio = (ini + fim) >> 1;
int p1 = query(no->l, l, r, ini, meio);
int p2 = query(no->r, l, r, meio+1, fim);
return p1 + p2;
}
node* version[maxn];
int nv, ver[maxn];
void init(int N, int A[], int B[]) {
n = N;
for (int i = 1; i <= n; i++)
v[i] = {A[i-1], B[i-1]};
sort(v+1, v+n+1);
int last = 0;
for (int i = 1; i <= n; i++) {
if (v[i].ff != last) {
ver[last] = nv;
last = v[i].ff;
}
version[++nv] = new node;
update(version[nv-1], version[nv], v[i].ss, 1);
}
ver[last] = nv;
for (int i = 1; i <= n; i++)
ver[i] = max(ver[i-1], ver[i]);
//cout << "OI " << nv << '\n';
//for (int i = 1; i <= n; i++)
//cout << ver[i] << " \n"[i==nv];
}
int qtd[maxn];
typedef long long ll;
ll dp[maxn];
int freq[maxn];
int lc=-1, inic=-1, fimc=-1;
ll cache;
inline ll solve(int l, int r, int ini, int fim) {
if (l != lc || ini != inic || fim != fimc) {
lc = l, inic = ini, fimc = fim;
cache = query(version[ ver[l] ], ini, fim);
}
return query(version[ ver[r] ], ini, fim) - cache;
}
int can(int M, int K[]) {
static vector<int> q;
q.clear();
ll sum = 0;
for (int i = 0; i < M; i++)
q.push_back(K[i]), sum += K[i];
if (sum > n) return 0;
for (auto& e : q)
freq[e]++;
sort(q.begin(), q.end());
q.erase(unique(q.begin(), q.end()), q.end());
bool certo = true;
int m = (int)q.size(); // m < sqrt(M)
for (int i = 0; i < m; i++) {
ll f = 1ll*freq[q[i]]*q[i]; // numero de caras na esquerda
dp[i] = solve(0, q[i], q[i], n) - f;
for (int j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + solve(q[j], q[i], q[i], n) - f);
if (dp[i] < 0) { // vizinhanca menor que 0
certo = false;
break;
}
}
for (int i = 0; i < m; i++)
dp[i] = 0;
for (auto& e : q)
freq[e] = 0;
return certo;
}
// matching perfeito ( teorema de hall )
// S(vizinhanca de A) >= S(A) para todo o subset
