#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define vt vector
#ifdef LOCAL
void print() {cerr << ']' << endl;}
template<typename Head, typename... Tail> void print(Head H, Tail... T) {cerr << ' ' << H; if(sizeof...(T)) cerr << ','; print(T...); }
template<typename T> ostream& operator << (ostream& os, vector<T> v){os << "["; bool first = 1; for(auto x : v) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator <<(ostream& os,pair<A, B> p) {return os << "(" << p.first << ", " << p.second << ")"; return os;}
template<typename A, typename B, typename C> ostream& operator << (ostream& os, tuple<A, B, C> a) {os << '(' << get<0>(a) << ", " << get<1>(a) << ", " << get<2>(a) << ")"; return os;}
template<typename A, size_t S> ostream& operator << (ostream& os, array<A, S> a) {os << "["; bool first = 1; for(auto x : a) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A> ostream& operator << (ostream& os, set<A> s) {os << "["; bool first = 1; for(auto x : s) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
template<typename A, typename B> ostream& operator << (ostream& os, map<A, B> m) {os << "["; bool first = 1; for(auto x : m) {if(!first) os << ", "; os << x; first = 0;} os << "]"; return os;}
#define dbg(...) cerr << '[' << #__VA_ARGS__ << ":", print(__VA_ARGS__);
#else
#define dbg(...)
#endif // LOCAL
const int INF = 1e9 + 5;
struct SegTree
{
vt<set<pair<int, int>>> S;
int N;
SegTree(int _N)
{
N = 1;
while(N < _N) N *= 2;
S = vt<set<pair<int, int>>>(2 * N);
}
void upd(int i, int x)
{
int u = i + N - 1;
assert(S[u].size() <= 1);
auto prev = S[u].empty() ? make_pair(INF, -1) : *S[u].begin();
auto current = make_pair(x, i);
for( ; u > 0; u /= 2)
{
S[u].erase(prev);
S[u].insert(current);
}
}
void del(int i)
{
upd(i, INF);
}
pair<int, int> qry(int l, int r, int x, int a, int b, int i)
{
if(l <= a && b <= r)
{
auto it = S[i].lower_bound(make_pair(x, -1));
if(it == S[i].end()) return make_pair(INF, -1);
return *it;
}
if(r < a || b < l) return make_pair(INF, -1);
int m = (a + b) / 2;
return min(qry(l, r, x, a, m, 2 * i), qry(l, r, x, m + 1, b, 2 * i + 1));
}
pair<int, int> qry(int l, int r, int x) {return qry(l, r, x, 1, N, 1);}
};
vt<pair<int, int>> v;
int N;
SegTree s(1);
void init(int _N, int A[], int B[])
{
N = _N;
v = vt<pair<int, int>>(N);
for(int i = 0; i < N; i++)
{
v[i].first = A[i];
v[i].second = B[i];
}
sort(v.begin(), v.end());
s = SegTree(N);
for(int i = 0; i < N; i++)
{
s.upd(i + 1, v[i].second);
}
}
int can(int M, int K[]) {
sort(K, K + M);
long long sum = 0;
for(int i = 0; i < M; i++) sum += K[i];
if(sum > N)
{
return 0;
}
vt<pair<int, int>> changed;
bool ok = 1;
for(int i = 0; i < M && ok; i++)
{
int j = upper_bound(v.begin(), v.end(), make_pair(K[i] + 1, -1)) - v.begin() - 1;
//while(j + 1 < N && v[j + 1].first <= K[i]) j++;
int rem = K[i];
while(rem > 0)
{
auto cur = s.qry(1, j + 1, K[i]);
if(cur.second == -1 || cur.first == INF)
{
ok = 0;
break;
}
rem--;
assert(1 <= cur.second && cur.second <= N);
changed.push_back(make_pair(cur.second, cur.first));
s.del(cur.second);
}
}
for(auto [a, b] : changed) s.upd(a, b);
return ok;
}
/*
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _N;
cin >> _N;
int A[_N], B[_N];
for(int i = 0; i < _N; i++) cin >> A[i] >> B[i];
init(_N, A, B);
int Q;
cin >> Q;
for(int _i = 0; _i < Q; _i++)
{
int M;
cin >> M;
int sizes[M];
for(int i = 0; i < M; i++) cin >> sizes[i];
cout << can(M, sizes) << "\n";
}
}
*/
/*
4
2 4
1 2
2 3
2 3
1
2 1 3
*/
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1
*/
