#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <algorithm>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <cassert>
#pragma GCC target("avx2,bmi,bmi,popcnt,lzcnt")
using namespace std;
using namespace __gnu_pbds;
#define all(x) (x).begin(), (x).end()
using ll = long long;
using ld = long double;
//#define int ll
using pii = pair<int, int>;
#define fr first
#define sc second
const int N = 15e4 + 5, inf = 1e9 + 5;
set<pii> av[8];
set<pii> taken[3][8];
int msks[N], xs[N], n;
pair<int, ll> curr;
void printAll(string message) {
cout << message << '\n';
cout << "Curr: " << curr.fr << " " << curr.sc << '\n';
cout << "Av:\n";
for (int i = 0; i < 8; i ++) {
cout << i << ": ";
for (auto j : av[i])
cout << j.fr << " ";
cout << '\n';
}
cout << "Taken\n";
for (int k = 0; k < 3; k ++) {
cout << "TakenK: " << k << '\n';
for (int i = 0; i < 8; i ++) {
cout << i << ": ";
for (auto j : taken[k][i])
cout << j.fr << " ";
cout << '\n';
}
}
}
bool add(int x) {
int minn = inf;
for (int i = 0; i < 8; i ++)
if (i & (1 << x) && !av[i].empty() && minn > (*av[i].begin()).fr)
minn = (*av[i].begin()).fr;
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int costAdaug = inf;
bool potSchimb = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
costAdaug = (*av[i].begin()).fr;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
potSchimb = 1;
if (potSchimb)
minn = min(minn, costAdaug);
}
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int z = 3 - x - y;
int costAdaug = inf;
bool potSchimbZY = 0;
bool potSchimbYX = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << z) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
costAdaug = (*av[i].begin()).fr;
for (int i = 0; i < 8; i ++)
if (i & (1 << z) && i & (1 << y) && !taken[z][i].empty())
potSchimbZY = 1;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
potSchimbYX = 1;
if (potSchimbYX && potSchimbZY)
minn = min(minn, costAdaug);
}
if (minn >= inf)
return false;
curr.sc += minn;
curr.fr ++;
for (int i = 0; i < 8; i ++)
if (i & (1 << x) && !av[i].empty() && minn == (*av[i].begin()).fr) {
taken[x][i].insert(*av[i].begin());
av[i].erase(av[i].begin());
return true;
}
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int costAdaug = inf, deUnde = -1, ad = -1;
bool potSchimb = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
costAdaug = (*av[i].begin()).fr, ad = i;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
potSchimb = 1, deUnde = i;
if (potSchimb && costAdaug == minn) {
pii sus = *taken[y][deUnde].begin();
taken[y][deUnde].erase(sus);
taken[x][deUnde].insert(sus);
sus = *av[ad].begin();
av[ad].erase(sus);
taken[y][ad].insert(sus);
return true;
}
}
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int z = 3 - x - y;
int costAdaug = inf, deUndeYX = -1, deUndeZY = -1, ad = -1;
bool potSchimbZY = 0;
bool potSchimbYX = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << z) && !av[i].empty() && costAdaug > (*av[i].begin()).fr)
costAdaug = (*av[i].begin()).fr, ad = i;
for (int i = 0; i < 8; i ++)
if (i & (1 << z) && i & (1 << y) && !taken[z][i].empty())
potSchimbZY = 1, deUndeZY = i;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << x) && !taken[y][i].empty())
potSchimbYX = 1, deUndeYX = i;
if (potSchimbYX && potSchimbZY && minn == costAdaug) {
pii sus = *taken[z][deUndeZY].begin();
taken[z][deUndeZY].erase(sus);
taken[y][deUndeZY].insert(sus);
sus = *taken[y][deUndeYX].begin();
taken[y][deUndeYX].erase(sus);
taken[x][deUndeYX].insert(sus);
sus = *av[ad].begin();
av[ad].erase(sus);
taken[z][ad].insert(sus);
return true;
}
}
assert(false);
}
bool rem(int x) {
int maxx = -1;
for (int i = 0; i < 8; i ++)
if (i & (1 << x) && !taken[x][i].empty() && maxx < (*taken[x][i].rbegin()).fr)
maxx = (*taken[x][i].rbegin()).fr;
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int costScot = -1;
bool potSchimb = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && !taken[y][i].empty() && costScot < (*taken[y][i].rbegin()).fr)
costScot = (*taken[y][i].rbegin()).fr;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << x) && !taken[x][i].empty())
potSchimb = 1;
if (potSchimb)
maxx = max(maxx, costScot);
}
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int z = 3 - x - y;
int costScot = -1;
bool potSchimbYZ = 0;
bool potSchimbXY = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << z) && !taken[z][i].empty() && costScot < (*taken[z][i].rbegin()).fr)
costScot = (*taken[z][i].rbegin()).fr;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << z) && !taken[y][i].empty())
potSchimbYZ = 1;
for (int i = 0; i < 8; i ++)
if (i & (1 << x) && i & (1 << y) && !taken[x][i].empty())
potSchimbXY = 1;
if (potSchimbXY && potSchimbYZ)
maxx = max(maxx, costScot);
}
if (maxx == -1)
return false;
//cout << "rem: " << maxx << '\n';
curr.sc -= maxx;
curr.fr --;
for (int i = 0; i < 8; i ++)
if (i & (1 << x) && !taken[x][i].empty() && maxx == (*taken[x][i].rbegin()).fr) {
av[i].insert(*taken[x][i].rbegin());
taken[x][i].erase(*taken[x][i].rbegin());
return true;
}
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int costScot = -1, ad = 0, deUnde = 0;
bool potSchimb = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && !taken[y][i].empty() && costScot < (*taken[y][i].rbegin()).fr)
costScot = (*taken[y][i].rbegin()).fr, ad = i;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << x) && !taken[x][i].empty())
potSchimb = 1, deUnde = i;
if (potSchimb && costScot == maxx) {
pii sus = *taken[x][deUnde].rbegin();
taken[x][deUnde].erase(sus);
taken[y][deUnde].insert(sus);
sus = *taken[y][ad].rbegin();
av[ad].insert(sus);
taken[y][ad].erase(sus);
return true;
}
}
for (int y = 0; y < 3; y ++) {
if (x == y)
continue;
int z = 3 - x - y;
int costScot = -1, ad = 0, deUndeXY = 0, deUndeYZ = 0;
bool potSchimbYZ = 0;
bool potSchimbXY = 0;
for (int i = 0; i < 8; i ++)
if (i & (1 << z) && !taken[z][i].empty() && costScot < (*taken[z][i].rbegin()).fr)
costScot = (*taken[z][i].rbegin()).fr, ad = i;
for (int i = 0; i < 8; i ++)
if (i & (1 << y) && i & (1 << z) && !taken[y][i].empty())
potSchimbYZ = 1, deUndeYZ = i;
for (int i = 0; i < 8; i ++)
if (i & (1 << x) && i & (1 << y) && !taken[x][i].empty())
potSchimbXY = 1, deUndeXY = i;
if (potSchimbXY && potSchimbYZ && costScot == maxx) {
pii sus = *taken[y][deUndeYZ].rbegin();
taken[y][deUndeYZ].erase(sus);
taken[z][deUndeYZ].insert(sus);
sus = *taken[x][deUndeXY].rbegin();
taken[x][deUndeXY].erase(sus);
taken[y][deUndeXY].insert(sus);
sus = *taken[z][ad].rbegin();
av[ad].insert(sus);
taken[z][ad].erase(sus);
return true;
}
}
assert(false);
}
bool add1() {
if (!add(0)) {
return false;
}
if (!add(1)) {
rem(0);
return false;
}
if (!add(1)) {
rem(0);
rem(1);
return false;
}
if (!add(2)) {
rem(0);
rem(1);
rem(1);
return false;
}
return true;
}
bool add2() {
if (!add(0)) {
return false;
}
if (!add(1)) {
rem(0);
return false;
}
if (!add(2)) {
rem(0);
rem(1);
return false;
}
if (!add(2)) {
rem(0);
rem(1);
rem(2);
return false;
}
return true;
}
bool remove1() {
int sum1 = 0, sum2 = 0;
for (int i = 0; i < 8; i ++) {
sum1 += taken[1][i].size();
sum2 += taken[2][i].size();
}
if (sum2 == 2 * sum1)
return false;
if (!rem(0)) {
return false;
}
if (!rem(1)) {
add(0);
return false;
}
if (!rem(1)) {
add(0);
add(1);
return false;
}
if (!rem(2)) {
add(0);
add(1);
add(1);
return false;
}
return true;
}
bool remove2() {
int sum1 = 0, sum2 = 0;
for (int i = 0; i < 8; i ++) {
sum1 += taken[1][i].size();
sum2 += taken[2][i].size();
}
if (2 * sum2 == sum1)
return false;
if (!rem(0)) {
return false;
}
if (!rem(1)) {
add(0);
return false;
}
if (!rem(2)) {
add(0);
add(1);
return false;
}
if (!rem(2)) {
add(0);
add(1);
add(2);
return false;
}
return true;
}
bool swap12() {
if (!rem(1))
return false;
if (!add(2)) {
add(1);
return false;
}
return true;
}
bool swap21() {
if (!rem(2))
return false;
if (!add(1)) {
add(2);
return false;
}
return true;
}
pair<int, ll> better(pair<int, ll> a, pair<int, ll> b) {
if (a.fr > b.fr)
return a;
if (a.fr < b.fr)
return b;
if (a.sc < b.sc)
return a;
return b;
}
ll update(int pos, int val) { //ideea e ca se schimba putine chestii
int sum1 = 0, sum2 = 0;
for (int i = 0; i < 8; i ++) {
sum1 += taken[1][i].size();
sum2 += taken[2][i].size();
}
if (av[msks[pos]].count({xs[pos], pos})) {
av[msks[pos]].erase({xs[pos], pos});
xs[pos] = val;
av[msks[pos]].insert({xs[pos], pos});
} else {
int loc = 0;
if (taken[1][msks[pos]].count({xs[pos], pos}))
loc = 1;
if (taken[2][msks[pos]].count({xs[pos], pos}))
loc = 2;
if (2 * sum1 != sum2) {
vector<int> f = {1, 2, 1};
f[loc] --;
taken[loc][msks[pos]].erase({xs[pos], pos});
curr.fr --;
curr.sc -= xs[pos];
for (int i = 0; i < 3; i ++)
while (f[i] --)
rem(i);
xs[pos] = val;
av[msks[pos]].insert({val, pos});
add1();
} else {
vector<int> f = {1, 1, 2};
f[loc] --;
taken[loc][msks[pos]].erase({xs[pos], pos});
curr.fr --;
curr.sc -= xs[pos];
for (int i = 0; i < 3; i ++)
while (f[i] --)
rem(i);
xs[pos] = val;
av[msks[pos]].insert({val, pos});
add2();
}
}
if (remove1())
add1();
if (remove2())
add2();
pair<int, ll> ans = curr;
if (swap12()) {
if (better(ans, curr) == ans)
swap21();
ans = curr;
}
if (swap21()) {
if (better(ans, curr) == ans)
swap12();
ans = curr;
}
return ans.sc;
}
pair<int, ll> solve() {
for (int i = 0; i < n; i ++)
av[msks[i]].insert({xs[i], i});
pair<int, ll> ans = {0, 0};
curr = {0, 0};
while (1) {
ans = better(ans, curr);
if (!add1())
break;
}
while (1) {
ans = better(ans, curr);
if (add2())
continue;
if (swap12())
continue;
break;
}
for (int i = 0; i < 8; i ++) {
av[i].clear();
for (int j = 0; j < 3; j ++)
taken[j][i].clear();
}
for (int i = 0; i < n; i ++)
av[msks[i]].insert({xs[i], i});
curr = {0, 0};
while (1) {
if (ans == curr)
break;
if (!add1())
break;
}
while (1) {
if (ans == curr)
break;
if (add2())
continue;
if (swap12())
continue;
break;
}
return {ans.fr / 4, ans.sc};
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i ++) {
int msk, x;
cin >> msk >> x;
int sus = 0;
if (msk >= 100) {
msk -= 100;
sus ++;
}
if (msk >= 10) {
msk -= 10;
sus += 2;
}
if (msk) {
msk --;
sus += 4;
}
msks[i] = sus;
xs[i] = x;
}
pair<int, ll> ans = solve();
cout << ans.fr << " " << ans.sc << '\n';
int q;
cin >> q;
while (q --) {
int x, y;
cin >> x >> y;
ll sus = update(x - 1, y);
cout << sus << '\n';
}
}
/*
fac o chestie de genu
fac for prin numarul de echipe <- cred ca e usor calculabil
apoi fixez numarul de echipe cu 2 matematicieni
daca calculez corect numarul ce se intampla pentru asta,
ca sa pot schimba un matematician la informatician am mai multe variante:
iau cel mai ieftin informatician de pe bara {
dau afara un matematician SAU
transform un matematician in ciucuiala, ciucuiala e dat afara
} SAU {
transform un matematician in informatician
transform un ciucuiala in informatician {
iau un ciucuiala de pe bara si dau afara un matematician
transform un matematician in ciucuiala
}
} -> merge pentru Q = 0, 53 pct, mai mult ca suficient
acuma numarul de echipe cum il fac :/
fac greeeeeeeeedy
imi fac prima data o echipa
apoi inca una
sinca una
...
ideea e ca eu o sa am nevoie de update-uri de tipul:
scoate X optim
baga X optim
scoate e usor, scoti al mai ieftin -> fals
la baga X : {
bagi cel mai ieftin X de pe bara
bagi Y, schimbi Y in X
bagi Z, schimbi Z in Y, schimbi Y in X
}
la scoate X : {
scoti cel mai scump X
scoti Y, schimbi X in Y
scoti Z, schimbi X in Y, schimbi Y in Z
}
-> daca asta e corect, nu cred ca e atat de deep
am nevoie acum sa fac subtask-ul 2
nr de echipe
*/
