#include <iostream>
#include <fstream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <stack>
#include <map>
#include <unordered_map>
#include <climits>
using namespace std;
class Graf {
vector<vector<int>> listeAdiacenta;
vector<vector<int>> flux;
vector<vector<int>> capacitate;
int bfs(const int& sursa, const int& destinatie, vector<int>& parinte) {
for (int i=0; i<parinte.size(); i++ ){
parinte[i] = -1;
}
parinte[sursa] = -2;
queue<pair<int, int>> q;
q.push({sursa, INT_MAX});
while (!q.empty()) {
int nodCurent = q.front().first;
int fluxCurent = q.front().second;
q.pop();
for (int vecin : listeAdiacenta[nodCurent]) {
if (parinte[vecin] == -1 && capacitate[nodCurent][vecin] > flux[nodCurent][vecin]) {
parinte[vecin] = nodCurent;
int fluxMinim = min(fluxCurent, capacitate[nodCurent][vecin] - flux[nodCurent][vecin]);
if (vecin == destinatie) {
return fluxMinim;
}
q.push({vecin, fluxMinim});
}
}
}
return 0;
}
public:
Graf(int n) {
this->listeAdiacenta = vector<vector<int>>(n);
this->capacitate = vector<vector<int>>(n, vector<int>(n));
this->flux = vector<vector<int>>(n, vector<int>(n));
}
Graf(vector<vector<int>>& listeAdiacenta, vector<vector<int>>& capacitate) {
this->listeAdiacenta = listeAdiacenta;
this->capacitate = capacitate;
flux = vector<vector<int>>(capacitate.size(), vector<int>(capacitate.size(), 0));
}
void adaugaMuchie(int start, int destinatie, int capacitate) {
listeAdiacenta[start].push_back(destinatie);
listeAdiacenta[destinatie].push_back(start);
this->capacitate[start][destinatie] = capacitate;
}
int fluxMaxim(const int& sursa, const int& destinatie) {
vector<int> parinte(capacitate.size(), -1);
int fluxMaxim = 0;
while(true) {
int fluxGasit = bfs(sursa, destinatie, parinte);
if (!fluxGasit) {
break;
}
fluxMaxim += fluxGasit;
int nodCurent = destinatie;
while(nodCurent != sursa) {
int parinteNodCurent = parinte[nodCurent];
flux[parinteNodCurent][nodCurent] += fluxGasit;
flux[nodCurent][parinteNodCurent] -= fluxGasit;
nodCurent = parinteNodCurent;
}
}
return fluxMaxim;
}
vector<int> intersectii(const int& start) {
vector<int> vizitati(capacitate.size(), 0);
vizitati[start] = 1;
queue<int> q;
q.push(start);
while (!q.empty()) {
int nodCurent = q.front();
q.pop();
for (int vecin : listeAdiacenta[nodCurent]) {
if (!vizitati[vecin] && capacitate[nodCurent][vecin] > flux[nodCurent][vecin]) {
vizitati[vecin] = 1;
q.push(vecin);
}
}
}
return vizitati;
}
vector<vector<int>> getFlux() {
return flux;
}
};
class Solutie {
void dfs(string aeroport, map<string, priority_queue<string, vector<string>, greater<string>>>& graf,
vector<string>& itinerariu) {
while (!graf[aeroport].empty()) {
string urmator = graf[aeroport].top();
graf[aeroport].pop();
dfs(urmator, graf, itinerariu);
}
itinerariu.push_back(aeroport);
}
public:
void Harta() {
ifstream f("harta.in");
ofstream g("harta.out");
int n, x, y;
f>>n;
vector<vector<int>> listeAdiacenta(n+n+2);
vector<vector<int>> capacitate(n+n+2, vector<int>(n+n+2, 0));
for (int i=1; i<=n; i++) {
f>>x>>y;
listeAdiacenta[0].push_back(i);
listeAdiacenta[i].push_back(0);
capacitate[0][i] = x;
listeAdiacenta[n+i].push_back(n+n+1);
listeAdiacenta[n+n+1].push_back(n+i);
capacitate[n+i][n+n+1] = y;
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
if (i == j)
continue;
listeAdiacenta[i].push_back(n+j);
listeAdiacenta[n+j].push_back(i);
capacitate[i][n+j] = 1;
}
}
Graf graf(listeAdiacenta, capacitate);
int fluxMaxim = graf.fluxMaxim(0, n+n+1);
g<<fluxMaxim<<'\n';
for (int i=1; i<=n; i++) {
for (int j=n+1; j<=n+n; j++) {
if (graf.getFlux()[i][j])
g<<i<<' '<<j-n<<'\n';
}
}
}
void Paznici() {
ifstream f("paznici.in");
ofstream g("paznici.out");
int n, m;
string linie;
f>>n>>m;
vector<vector<int>> listeAdiacenta(n+m+2);
vector<vector<int>> capacitate(n+m+2, vector<int>(n+m+2, 0));
for (int i=1; i<=n; i++) {
f>>linie;
for (int j=0; j<m; j++) {
if (linie[j] == '1') {
listeAdiacenta[i].push_back(n+j+1);
listeAdiacenta[n+j+1].push_back(i);
capacitate[i][n+j+1] = 1;
}
}
}
for (int i=1; i<=n; i++) {
listeAdiacenta[0].push_back(i);
listeAdiacenta[i].push_back(0);
capacitate[0][i] = 1;
}
for (int i=1; i<=m; i++) {
listeAdiacenta[n+i].push_back(n+m+1);
listeAdiacenta[n+m+1].push_back(n+i);
capacitate[n+i][n+m+1] = 1;
}
Graf graf(listeAdiacenta, capacitate);
graf.fluxMaxim(0, n+m+1);
vector<int> intersectii = graf.intersectii(0);
for (int i=0; i<n; i++) {
if (!intersectii[i+1]) {
g<<char('A' + i);
}
}
for (int i=n+1; i<n+m+1; i++) {
if (intersectii[i]) {
g<<char('a' + i - n - 1);
}
}
}
void Senat() {
ifstream f("senat.in");
ofstream g("senat.out");
string linie;
int n, m;
f>>n>>m;
vector<vector<int>> listaAdiacenta(n + m + 2);
vector<vector<int>> capacitati(n + m + 2, vector<int>(n + m + 2, 0));
getline(f, linie);
for (int i=1; i<=m; i++) {
getline(f, linie);
int nr = 0;
for (int j=0; j<linie.size(); j++) {
if (linie[j] != ' ') {
nr = nr * 10 + (linie[j] - '0');
}
else {
listaAdiacenta[nr].push_back(n + i);
listaAdiacenta[n + i].push_back(nr);
capacitati[nr][n + i] = 1;
nr = 0;
}
}
if (nr != 0) {
listaAdiacenta[nr].push_back(n + i);
listaAdiacenta[n + i].push_back(nr);
capacitati[nr][n + i] = 1;
}
}
for (int i=1; i<=n; i++) {
listaAdiacenta[0].push_back(i);
listaAdiacenta[i].push_back(0);
capacitati[0][i] = 1;
}
for (int i=n+1; i<=n+m; i++) {
listaAdiacenta[i].push_back(n+m+1);
listaAdiacenta[n+m+1].push_back(i);
capacitati[i][n+m+1] = 1;
}
Graf graf(listaAdiacenta, capacitati);
int flux = graf.fluxMaxim(0, n+m+1);
if (flux != m)
g<<0;
else {
for (int i=n+1; i<=n+m; i++) {
for (int j=1; j<=n+1; j++) {
if (graf.getFlux()[j][i]) {
g<<j<<"\n";
}
}
}
}
}
void Soldati() {
int n, m;
cin >> n >> m;
vector<int> ai(n), bi(n);
for (int& a : ai) cin >> a;
for (int& b : bi) cin >> b;
if (accumulate(ai.begin(), ai.end(), 0) != accumulate(bi.begin(), bi.end(), 0)) {
cout << "NO\n";
return;
}
Graf graf(2 * n + 2);
int totalBi = accumulate(bi.begin(), bi.end(), 0);
for (int i = 0; i < n; ++i) {
graf.adaugaMuchie(0, i + 1, bi[i]);
graf.adaugaMuchie(i + 1, n + i + 1, ai[i]);
graf.adaugaMuchie(n + i + 1, 2 * n + 1, ai[i]);
}
for (int i = 0; i < m; ++i) {
int p, q;
cin >> p >> q;
graf.adaugaMuchie(p, n + q, INT_MAX);
graf.adaugaMuchie(q, n + p, INT_MAX);
}
int flow = graf.fluxMaxim(0, 2 * n + 1);
if (flow < totalBi) {
cout << "NO\n";
return;
}
cout << "YES\n";
vector<vector<int>> flux = graf.getFlux();
for (int i = 1; i <= n; ++i) {
int soldiers_staying = flux[i][n + i];
for (int j = 1; j <= n; ++j) {
if (i == j) {
cout << soldiers_staying << ' ';
} else {
cout << -flux[n + i][j] << ' ';
}
}
cout << '\n';
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
map<string, priority_queue<string, vector<string>, greater<string>>> graf;
vector<string> itinerariu;
for (auto& bilet : tickets) {
graf[bilet[0]].push(bilet[1]);
}
dfs("JFK", graf, itinerariu);
reverse(itinerariu.begin(), itinerariu.end());
return itinerariu;
}
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
unordered_map<int, stack<int>> graf;
unordered_map<int, int> grad;
stack<int> drum;
vector<vector<int>> rezultat;
for (auto& pereche : pairs) {
graf[pereche[0]].push(pereche[1]);
grad[pereche[0]]++;
grad[pereche[1]]--;
}
int start = pairs[0][0];
for (auto& gr : grad) {
if (gr.second > 0) {
start = gr.first;
break;
}
}
drum.push(start);
while (!drum.empty()) {
int nod = drum.top();
if (!graf[nod].empty()) {
drum.push(graf[nod].top());
graf[nod].pop();
} else {
drum.pop();
if (!drum.empty()) {
rezultat.push_back({drum.top(), nod});
}
}
}
reverse(rezultat.begin(), rezultat.end());
return rezultat;
}
};
int main() {
Solutie s;
s.Harta();
return 0;
}