#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} istream &operator>>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} #endif using ll=long long; using ull=unsigned long long; using P=pair; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateistream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} templateistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcount(x) ll myceil(ll a,ll b){return (a+b-1)/b;} template auto vec(const int (&d)[n],const T &init=T()){ if constexpr (id(d,init)); else return init; } #ifdef LOCAL #include "debug.h" #else #define debug(...) static_cast(0) templateostream &operator<<(ostream &os,const pair&p){os<>testcase; for(int i=0;i struct Dinic{ private: struct edge{ int to,rev; T cap; }; int n; vector>g; vector>pos; template struct Q{ vectordata; int p; Q():p(0){} void push(T2 x){ data.push_back(x); } int front()const{ return data[p]; } void pop(){p++;} void clear(){ data.clear(); p=0; } bool empty()const{ return p==data.size(); } }; public: Dinic():n(0){} Dinic(int n):n(n),g(n){} void add_edge(int u,int v,T cap){ pos.push_back({u,g[u].size()}); int f=g[u].size(); int t=g[v].size(); if(u==v)t++; g[u].push_back({v,t,cap}); g[v].push_back({u,f,0}); } struct E{ int from,to; T cap,flow; }; vectoredges()const{ int m=pos.size(); vectorret(m); rep(i,m){ edge e=g[pos[i].first][pos[i].second]; edge r=g[e.to][e.rev]; ret[i]={pos[i].first,e.to,e.cap+r.cap,r.cap}; } return ret; } T flow(int s,int t,T limit){ assert(0<=s&&slevel(n),iter(n); Qque; auto bfs=[&](){ fill(all(level),-1); level[s]=0; que.clear(); que.push(s); while(!que.empty()){ int x=que.front(); que.pop(); for(auto e:g[x]){ if(e.cap==0||level[e.to]>=0)continue; level[e.to]=level[x]+1; if(e.to==t)return; que.push(e.to); } } }; functiondfs=[&](int v,T up)->T { if(v==s)return up; T ret=0; int lv=level[v]; reps(i,iter[v],g[v].size()){ edge e=g[v][i]; if(lv<=level[e.to]||g[e.to][e.rev].cap==0)continue; T d=dfs(e.to,min(up-ret,g[e.to][e.rev].cap)); if(d<=0)continue; g[v][i].cap+=d; g[e.to][e.rev].cap-=d; ret+=d; if(ret==up)return ret; } level[v]=n; return ret; }; T flow=0; while(flow::max()); } vectormin_cut(int s){ vectorret(n,false); Qque; que.push(s); while(!que.empty()){ int x=que.front(); que.pop(); ret[x]=true; for(auto e:g[x]){ if(e.cap&&!ret[e.to]){ ret[e.to]=true; que.push(e.to); } } } return ret; } }; void SOLVE(){ int n; cin>>n; Dinicg(n*2+2); int s=n*2,t=s+1; int sum=0; rep(i,n){ int b,c; cin>>b>>c; g.add_edge(s,i,c); g.add_edge(i,i+n,b+c); g.add_edge(i+n,t,b); sum+=b+c; } int m; cin>>m; rep(i,m){ int b,c; cin>>b>>c; g.add_edge(c+n,b,1e9); } cout<