#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;
const int maxnos = 1e7 + 10;
struct node {
int l, r;
int v;
node () {
l = r = 0;
v = 0;
}
};
vector<node> id;
inline int l(int t) {
return t ? id[t].l : 0;
}
inline int r(int t) {
return t ? id[t].r : 0;
}
inline int valor(int t) {
return t ? id[t].v : 0;
}
inline int lastpos(vector<node> const& vetor) {
return (int)vetor.size() - 1;
}
void build(int& no, int ini = 1, int fim = n) {
id.push_back(node()), no = lastpos(id);
if (ini == fim) return;
int meio = (ini + fim) / 2;
build(id[no].l, ini, meio);
build(id[no].r, meio+1, fim);
}
void update(int old, int no, int p, int v, int ini=1, int fim=n) {
if (ini == fim) {
id[no].v = valor(old) + v;
return;
}
int meio = (ini + fim) >> 1;
if (p <= meio) {
if (l(old) == 0) id.push_back(node()), id[no].l = lastpos(id);
else id.push_back(node( id[l(old)] )), id[no].l = lastpos(id);
if(r(old)) id[no].r = id[old].r;
update(l(old), id[no].l, p, v, ini, meio);
}else {
if (r(old) == 0) id.push_back(node()), id[no].r = lastpos(id);
else id.push_back(node( id[r(old)] )), id[no].r = lastpos(id);
if(l(old)) id[no].l = id[old].l;
update(r(old), id[no].r, p, v, meio+1, fim);
}
id[no].v = valor(id[no].l) + valor(id[no].r);
}
int query(int no, int l, int r, int ini=1, int fim=n) {
if(no == 0 || ini > r || fim < l) return 0;
if(l <= ini && fim <= r) return id[no].v;
int meio = (ini + fim) >> 1;
int p1 = query(id[no].l, l, r, ini, meio);
int p2 = query(id[no].r, l, r, meio+1, fim);
return p1 + p2;
}
int 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 no;
id.push_back(node());
build(no);
int last = 0;
for (int i = 1; i <= n; i++) {
if (v[i].ff != last) {
ver[last] = nv;
last = v[i].ff;
}
id.push_back(node());
version[++nv] = lastpos(id);
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];
inline ll solve(int l, int r, int ini, int fim) {
return query(version[ ver[r] ], ini, fim) - (l>0?query(version[ ver[l] ], ini, fim):0);
}
int can(int M, int K[]) {
vector<int> q;
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
