Cod sursa(job #579969)
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 210;
int S, D, n, t[N], cap[N][N], flux[N][N];
bool viz[N];
queue<int> Q;
vector<int> v[N];
void read() {
int x, y, nrm = 0;
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) {
scanf("%d %d", &x, &y);
nrm += x;
cap[0][i] = x;
cap[n + i][2 * n + 1] = y;
}
printf("%d\n", nrm);
}
void init() {
S = 0;
D = 2 * n + 1;
for (int j = 1; j <= n; ++ j) {
v[S].push_back(j);
v[j].push_back(S);
}
for (int i = 1; i <= n; ++ i) {
v[n + i].push_back(D);
v[D].push_back(n + i);
}
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (i != j) {
v[i].push_back(n + j);
v[n + j].push_back(i);
cap[i][n + j] = 1;
}
}
int min(int x, int y) {
return x < y ? x : y;
}
int calculeaza(int nod) {
int rez = 2000000000;
for (int i = nod; i; i = t[i])
rez = min(rez, cap[t[i]][i] - flux[t[i]][i]);
return rez;
}
void propaga(int nod, int fl) {
for (int i = nod; i; i = t[i]) {
flux[t[i]][i] += fl;
flux[i][t[i]] -= fl;
}
}
bool BFS() {
int nc;
viz[S] = 1;
Q.push(S);
while (! Q.empty()) {
nc = Q.front();
Q.pop();
if (nc == D)
continue;
for (vector <int> :: iterator it = v[nc].begin(); it != v[nc].end(); ++ it)
if (! viz[*it] && flux[nc][*it] < cap[nc][*it]) {
viz[*it] = 1;
t[*it] = nc;
Q.push(*it);
}
}
return viz[D];
}
void reset() {
for (int i = S; i <= D; ++ i) {
t[i] = 0;
viz[i] = 0;
}
}
void maxflow() {
int minf;
while (BFS()) {
for (vector <int> :: iterator it = v[D].begin(); it != v[D].end(); ++ it)
if (viz[*it]) {
minf = min(cap[*it][D] - flux[*it][D], calculeaza(*it));
flux[*it][D] += minf;
flux[D][*it] -= minf;
propaga(*it, minf);
}
reset();
}
}
void afis() {
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= n; ++ j)
if (flux[i][n + j] == 1)
printf("%d %d\n", i, j);
}
int main() {
read();
init();
maxflow();
afis();
return 0;
}