Cod sursa(job #479499)
#include <cstring>
#include <fstream>
#include <utility>
#include <queue>
using namespace std;
void Read();
void Solve();
bool FindPath();
void Augment();
void Write();
int n;
int c[202][202], f[202][202], t[202];
bool s[202];
queue<int> q;
int tot;
int main()
{
Read();
Solve();
Write();
}
void Read()
{
ifstream fin("harta.in");
fin >> n;
for (int i = 1, g1, g2; i <= n; ++i)
{
fin >> g1 >> g2;
c[0][i] = g1;
c[i + n][2 * n + 1] = g2;
tot += g1;
}
fin.close();
}
void Solve()
{
for (int i = 1; i <= n; ++i)
for (int j = n + 1; j <= 2 * n; ++j)
if (i != j - n)
c[i][j] = 1;
while (FindPath())
Augment();
}
bool FindPath()
{
memset(s, 0, sizeof(s));
while (!q.empty()) q.pop();
q.push(0);
s[0] = true;
while (!q.empty())
{
int i = q.front(); q.pop();
for (int j = 1; j <= 2 * n + 1; ++j)
if (!s[j])
if (f[i][j] < c[i][j])
{
t[j] = i;
s[j] = true;
if (j == 2 * n + 1) return true;
q.push(j);
}
}
return false;
}
void Augment()
{
int i, j;
for (i = 2 * n + 1, j = t[2 * n + 1]; i != 0; i = t[i], j = t[j])
++f[j][i], --f[i][j];
}
void Write()
{
ofstream fout("harta.out");
fout << tot << '\n';
for (int i = 1; i <= n; ++i)
for (int j = n + 1; j <= 2 * n; ++j)
if (f[i][j])
fout << i << ' ' << j - n << '\n';
fout.close();
}