#include <stdio.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <stdio.h>
#include <string.h>
#include <assert.h>
using namespace std;
static const double EPS = 1e-9;
int ROUND(double x) { return (int)(x+0.5); }
bool ISINT(double x) { return fabs(ROUND(x)-x)<=EPS; }
bool ISEQUAL(double x,double y) { return fabs(x-y)<=EPS*max(1.0,max(fabs(x),fabs(y))); }
double SQSUM(double x,double y) { return x*x+y*y; }
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
#define PI (acos(-1))
#define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0]))
#define NG (-1)
#define BIG (987654321)
#define SZ(a) ((int)((a).size()))
#define SQ(a) ((a)*(a))
typedef long long ll;
typedef unsigned long long ull;
#define FOR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
// BEGIN CUT HERE
#undef FOR
#define FOR(v,i) for(auto i=(v).begin();i!=(v).end();++i)
// END CUT HERE
// 最大流 Dinic O(EV^2)だけど、実際もっとはやい。
class Dinic
{
public:
Dinic(int input_maxv) : maxv(input_maxv)
{
G.resize(input_maxv);
level.resize(input_maxv);
iter.resize(input_maxv);
}
void add_edge_both(int from, int to, int cap)
{
const int rev_from = SZ(G[from]);
const int rev_to = SZ(G[to]);
G[from].push_back(edge(to,cap,rev_to));
G[to].push_back(edge(from,cap,rev_from));
}
void add_edge(int from, int to, int cap)
{
const int rev_from = SZ(G[from]);
const int rev_to = SZ(G[to]);
G[from].push_back(edge(to,cap,rev_to));
G[to].push_back(edge(from,0,rev_from));
}
// sからtへの最大流を求める
int max_flow(int s, int t)
{
int flow = 0;
for(;;)
{
bfs(s);
if(level[t]<0) break;
fill(iter.begin(),iter.end(),0);
int f;
while( (f=dfs(s,t,DINIC_INF))>0)
{
flow += f;
}
}
return flow;
}
// ノードsから辿れる範囲を求める(これ以上流せないところcap=0は、リンクがなくなる)
// (流し終わったあとsourceからたどれる範囲が、最小カット時のs側。たどれない範囲がt側。その境界がカットするところ。)
vector <bool> get_nodes_in_group(int s)
{
vector <bool> ret(maxv);
queue<int> que;
que.push(s);
while(!que.empty())
{
int v = que.front();
que.pop();
ret[v]=true;
for(int i=0;i<SZ(G[v]);i++)
{
edge &e = G[v][i];
if(e.cap>0 && !ret[e.to])
{
que.push(e.to);
}
}
}
return ret;
}
void disp()
{
for (int v = 0; v < maxv; v++)
{
printf("%d:",v);
for(int i=0;i<SZ(G[v]);i++)
{
if(G[v][i].init_cap>0)
{
printf("->%d(%d),",G[v][i].to,G[v][i].init_cap);
}
}
printf("\n");
}
}
private:
// sからの最短距離をBFSで計算する
void bfs(int s)
{
fill(level.begin(),level.end(),NG);
queue<int> que;
level[s]=0;
que.push(s);
while(!que.empty())
{
int v = que.front();
que.pop();
for(int i=0;i<SZ(G[v]);i++)
{
edge &e = G[v][i];
if(e.cap>0 && level[e.to]<0)
{
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
// 増加パスをDFSで探す
int dfs(int v, int t, int f)
{
if(v==t) return f;
for (int &i=iter[v];i<SZ(G[v]);i++)
{
edge& e = G[v][i];
if(e.cap>0 && level[v]<level[e.to])
{
int d = dfs(e.to, t, min(f, e.cap));
if(d>0)
{
e.cap -= d;
G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
static const int DINIC_INF = INT_MAX; // 容量をllにしたいときは、ここも変える
struct edge
{
edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
int to; // 行先
int cap; // 容量
int rev; // 逆辺
int init_cap; // 初期容量(デバッグ用)
};
int maxv;
vector < vector <edge> > G; // グラフの隣接リスト
vector < int > level; // sからの距離
vector < int > iter; // どこまで調べ終わったか
};
int main()
{
int n;
cin >> n;
const int S = n;
const int T = S+1;
const int V = T+1;
{
Dinic* dinic = new Dinic(V);
for (int i = 0; i < n; i++)
{
int moyasu,umeru;
cin >> moyasu >> umeru;
dinic->add_edge(S,i,moyasu);
dinic->add_edge(i,T,umeru);
}
int answer = dinic->max_flow(S,T);
printf("%d\n",answer);
delete dinic;
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjbGltaXRzPgojaW5jbHVkZSA8Y2Zsb2F0PgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWVtb3J5PgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPHNzdHJlYW0+CiNpbmNsdWRlIDxjb21wbGV4PgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxzdGRpby5oPgojaW5jbHVkZSA8c3RyaW5nLmg+CiNpbmNsdWRlIDxhc3NlcnQuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0YXRpYyBjb25zdCBkb3VibGUgRVBTID0gMWUtOTsKaW50IFJPVU5EKGRvdWJsZSB4KSB7IHJldHVybiAoaW50KSh4KzAuNSk7IH0KYm9vbCBJU0lOVChkb3VibGUgeCkgeyByZXR1cm4gZmFicyhST1VORCh4KS14KTw9RVBTOyB9CmJvb2wgSVNFUVVBTChkb3VibGUgeCxkb3VibGUgeSkgeyByZXR1cm4gZmFicyh4LXkpPD1FUFMqbWF4KDEuMCxtYXgoZmFicyh4KSxmYWJzKHkpKSk7IH0KZG91YmxlIFNRU1VNKGRvdWJsZSB4LGRvdWJsZSB5KSB7IHJldHVybiB4KngreSp5OyB9CnRlbXBsYXRlPGNsYXNzIFQ+IGJvb2wgSU5SQU5HRShUIHgsVCBhLFQgYikgeyByZXR1cm4gYTw9eCYmeDw9YjsgfQojZGVmaW5lIFBJICAoYWNvcygtMSkpCiNkZWZpbmUgQVJSQVlfTlVNKGEpIChzaXplb2YoYSkvc2l6ZW9mKGFbMF0pKSAKI2RlZmluZSBORyAoLTEpCiNkZWZpbmUgQklHICg5ODc2NTQzMjEpCiNkZWZpbmUgU1ooYSkgKChpbnQpKChhKS5zaXplKCkpKQojZGVmaW5lIFNRKGEpICgoYSkqKGEpKQp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwoKI2RlZmluZSBGT1IodixpKSBmb3IoX190eXBlb2YoKHYpLmJlZ2luKCkpaT0odikuYmVnaW4oKTtpIT0odikuZW5kKCk7KytpKQovLyBCRUdJTiBDVVQgSEVSRQojdW5kZWYgRk9SCiNkZWZpbmUgRk9SKHYsaSkgZm9yKGF1dG8gaT0odikuYmVnaW4oKTtpIT0odikuZW5kKCk7KytpKQovLyBFTkQgQ1VUIEhFUkUKCi8vIOacgOWkp+a1gSBEaW5pYyBPKEVWXjIp44Gg44GR44Gp44CB5a6f6Zqb44KC44Gj44Go44Gv44KE44GE44CCCmNsYXNzIERpbmljCnsKcHVibGljOgoJRGluaWMoaW50IGlucHV0X21heHYpIDogbWF4dihpbnB1dF9tYXh2KQoJewoJCUcucmVzaXplKGlucHV0X21heHYpOwoJCWxldmVsLnJlc2l6ZShpbnB1dF9tYXh2KTsKCQlpdGVyLnJlc2l6ZShpbnB1dF9tYXh2KTsKCX0KCgl2b2lkIGFkZF9lZGdlX2JvdGgoaW50IGZyb20sIGludCB0bywgaW50IGNhcCkKCXsKCQljb25zdCBpbnQgcmV2X2Zyb20gID0gU1ooR1tmcm9tXSk7CgkJY29uc3QgaW50IHJldl90byAgICA9IFNaKEdbdG9dKTsKCQlHW2Zyb21dLnB1c2hfYmFjayhlZGdlKHRvLGNhcCxyZXZfdG8pKTsKCQlHW3RvXS5wdXNoX2JhY2soZWRnZShmcm9tLGNhcCxyZXZfZnJvbSkpOwoJfQoKCXZvaWQgYWRkX2VkZ2UoaW50IGZyb20sIGludCB0bywgaW50IGNhcCkKCXsKCQljb25zdCBpbnQgcmV2X2Zyb20gID0gU1ooR1tmcm9tXSk7CgkJY29uc3QgaW50IHJldl90byAgICA9IFNaKEdbdG9dKTsKCQlHW2Zyb21dLnB1c2hfYmFjayhlZGdlKHRvLGNhcCxyZXZfdG8pKTsKCQlHW3RvXS5wdXNoX2JhY2soZWRnZShmcm9tLDAscmV2X2Zyb20pKTsKCX0KCgkvLyBz44GL44KJdOOBuOOBruacgOWkp+a1geOCkuaxguOCgeOCiwoJaW50IG1heF9mbG93KGludCBzLCBpbnQgdCkKCXsKCQlpbnQgZmxvdyA9IDA7CgkJZm9yKDs7KQoJCXsKCQkJYmZzKHMpOwoJCQlpZihsZXZlbFt0XTwwKSBicmVhazsKCQkJZmlsbChpdGVyLmJlZ2luKCksaXRlci5lbmQoKSwwKTsKCQkJaW50IGY7CgkJCXdoaWxlKCAoZj1kZnMocyx0LERJTklDX0lORikpPjApCgkJCXsKCQkJCWZsb3cgKz0gZjsKCQkJfQoJCX0KCgkJcmV0dXJuIGZsb3c7Cgl9CgoJLy8gIOODjuODvOODiXPjgYvjgonovr/jgozjgovnr4Tlm7LjgpLmsYLjgoHjgovvvIjjgZPjgozku6XkuIrmtYHjgZvjgarjgYTjgajjgZPjgo1jYXA9MOOBr+OAgeODquODs+OCr+OBjOOBquOBj+OBquOCi++8iQoJLy8g77yI5rWB44GX57WC44KP44Gj44Gf44GC44Goc291cmNl44GL44KJ44Gf44Gp44KM44KL56+E5Zuy44GM44CB5pyA5bCP44Kr44OD44OI5pmC44Guc+WBtOOAguOBn+OBqeOCjOOBquOBhOevhOWbsuOBjHTlgbTjgILjgZ3jga7looPnlYzjgYzjgqvjg4Pjg4jjgZnjgovjgajjgZPjgo3jgILvvIkKCXZlY3RvciA8Ym9vbD4gZ2V0X25vZGVzX2luX2dyb3VwKGludCBzKQoJewoJCXZlY3RvciA8Ym9vbD4gcmV0KG1heHYpOwoKCQlxdWV1ZTxpbnQ+IHF1ZTsKCQlxdWUucHVzaChzKTsKCQl3aGlsZSghcXVlLmVtcHR5KCkpCgkJewoJCQlpbnQgdiA9IHF1ZS5mcm9udCgpOwoJCQlxdWUucG9wKCk7CgkJCXJldFt2XT10cnVlOwoKCQkJZm9yKGludCBpPTA7aTxTWihHW3ZdKTtpKyspCgkJCXsKCQkJCWVkZ2UgJmUgPSBHW3ZdW2ldOwoJCQkJaWYoZS5jYXA+MCAmJiAhcmV0W2UudG9dKQoJCQkJewoJCQkJCXF1ZS5wdXNoKGUudG8pOwoJCQkJfQoJCQl9CgkJfQoJCXJldHVybiByZXQ7Cgl9CgoJdm9pZCBkaXNwKCkKCXsKCQlmb3IgKGludCB2ID0gMDsgdiA8IG1heHY7IHYrKykKCQl7CgkJCXByaW50ZigiJWQ6Iix2KTsKCQkJZm9yKGludCBpPTA7aTxTWihHW3ZdKTtpKyspCgkJCXsKCQkJCWlmKEdbdl1baV0uaW5pdF9jYXA+MCkKCQkJCXsKCQkJCQlwcmludGYoIi0+JWQoJWQpLCIsR1t2XVtpXS50byxHW3ZdW2ldLmluaXRfY2FwKTsKCQkJCX0KCQkJfQoJCQlwcmludGYoIlxuIik7CgkJfQoJfQoKcHJpdmF0ZToKCS8vIHPjgYvjgonjga7mnIDnn63ot53pm6LjgpJCRlPjgafoqIjnrpfjgZnjgosKCXZvaWQgYmZzKGludCBzKQoJewoJCWZpbGwobGV2ZWwuYmVnaW4oKSxsZXZlbC5lbmQoKSxORyk7CgkJcXVldWU8aW50PiBxdWU7CgkJbGV2ZWxbc109MDsKCQlxdWUucHVzaChzKTsKCQl3aGlsZSghcXVlLmVtcHR5KCkpCgkJewoJCQlpbnQgdiA9IHF1ZS5mcm9udCgpOwoJCQlxdWUucG9wKCk7CgkJCWZvcihpbnQgaT0wO2k8U1ooR1t2XSk7aSsrKQoJCQl7CgkJCQllZGdlICZlID0gR1t2XVtpXTsKCQkJCWlmKGUuY2FwPjAgJiYgbGV2ZWxbZS50b108MCkKCQkJCXsKCQkJCQlsZXZlbFtlLnRvXSA9IGxldmVsW3ZdICsgMTsKCQkJCQlxdWUucHVzaChlLnRvKTsKCQkJCX0KCQkJfQoJCX0KCX0KCgkvLyDlopfliqDjg5HjgrnjgpJERlPjgafmjqLjgZkKCWludCBkZnMoaW50IHYsIGludCB0LCBpbnQgZikKCXsKCQlpZih2PT10KSByZXR1cm4gZjsKCQlmb3IgKGludCAmaT1pdGVyW3ZdO2k8U1ooR1t2XSk7aSsrKQoJCXsKCQkJZWRnZSYgZSA9IEdbdl1baV07CgkJCWlmKGUuY2FwPjAgJiYgbGV2ZWxbdl08bGV2ZWxbZS50b10pCgkJCXsKCQkJCWludCBkID0gZGZzKGUudG8sIHQsIG1pbihmLCBlLmNhcCkpOwoJCQkJaWYoZD4wKQoJCQkJewoJCQkJCWUuY2FwIC09IGQ7CgkJCQkJR1tlLnRvXVtlLnJldl0uY2FwICs9IGQ7CgkJCQkJcmV0dXJuIGQ7CgkJCQl9CgkJCX0KCQl9CgkJcmV0dXJuIDA7Cgl9CgoJc3RhdGljIGNvbnN0IGludCBESU5JQ19JTkYgPSBJTlRfTUFYOyAvLyDlrrnph4/jgpJsbOOBq+OBl+OBn+OBhOOBqOOBjeOBr+OAgeOBk+OBk+OCguWkieOBiOOCiwoKCXN0cnVjdCBlZGdlIAoJewoJCWVkZ2UoaW50IGlucHV0X3RvLCBpbnQgaW5wdXRfY2FwLCBpbnQgaW5wdXRfcmV2KSA6IHRvKGlucHV0X3RvKSwgY2FwKGlucHV0X2NhcCksIHJldihpbnB1dF9yZXYpLCBpbml0X2NhcChpbnB1dF9jYXApIHt9CgkJaW50IHRvOyAgICAgLy8g6KGM5YWICgkJaW50IGNhcDsgICAgLy8g5a656YePCgkJaW50IHJldjsgICAgLy8g6YCG6L66CgkJaW50IGluaXRfY2FwOyAvLyDliJ3mnJ/lrrnph4/vvIjjg4fjg5Djg4PjgrDnlKjvvIkKCX07CgoJaW50IG1heHY7Cgl2ZWN0b3IgPCB2ZWN0b3IgPGVkZ2U+ID4gRzsgLy8g44Kw44Op44OV44Gu6Zqj5o6l44Oq44K544OICgl2ZWN0b3IgPCBpbnQgPiBsZXZlbDsgICAgIC8vIHPjgYvjgonjga7ot53pm6IKCXZlY3RvciA8IGludCA+IGl0ZXI7ICAgICAgLy8g44Gp44GT44G+44Gn6Kq/44G557WC44KP44Gj44Gf44GLCgp9OwoKaW50IG1haW4oKQp7CglpbnQgbjsKCWNpbiA+PiBuOwoKCWNvbnN0IGludCBTID0gbjsKCWNvbnN0IGludCBUID0gUysxOwoJY29uc3QgaW50IFYgPSBUKzE7CgoJewoJCURpbmljKiBkaW5pYyA9IG5ldyBEaW5pYyhWKTsKCQlmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCQl7CgkJCWludCBtb3lhc3UsdW1lcnU7CgkJCWNpbiA+PiBtb3lhc3UgPj4gdW1lcnU7CgkJCWRpbmljLT5hZGRfZWRnZShTLGksbW95YXN1KTsKCQkJZGluaWMtPmFkZF9lZGdlKGksVCx1bWVydSk7CgkJfQoJCWludCBhbnN3ZXIgPSBkaW5pYy0+bWF4X2Zsb3coUyxUKTsKCQlwcmludGYoIiVkXG4iLGFuc3dlcik7CgoJCWRlbGV0ZSBkaW5pYzsKCX0KCglyZXR1cm4gMDsKfQo=