% Petrozavodsk, ASC contest
% http://acm.spbgu.ru/cgi-bin/monitor.pl/m080128.dat, problem B

\begin{problem}{Автомойка}{carwash.in}{carwash.out}{2 seconds}{256 megabytes}

% Author: Andrew Stankevich
% Translation: Sergey Kopeliovich

Бен -- владелец автомойки. Бен предлагает мойку и чистку салона машин.
Его автомойка расположена в столице Ранглии, поэтому он часто обслуживает
клиентов из столицы. Недавно он получил важный и весьма большой заказ
на мойку и чистку $n$ машин. Этот заказ должен быть обработан как можно быстрее! 

% Ben is the owner of a car wash. Ben offers car washing and 
% dry-cleaning of the car compartment. His wash is located in the capital
% of Edgeland, and he often serves clients from government. Recently
% Ben has received an order of washing and dry-cleaning of $n$ cars.
% And this order must be executed as fast as possible!

\vspace*{0.5em}
Предварительное исследование показало, что $i$-ю машину нужно мыть $a_i$ минут,
чистить $b_i$ минут. Мойка и чистка происходят в разных зданиях, поэтому нельзя
одну машину одновременно и мыть, и чистить.
Порядок этих двух операций для каждой из машин не важен.
Также не важен порядок мойки машин и порядок чистки машин.
У Бена есть два рабочих -- Том и Джери. Том моет, Джери чистит.
Требования качества обязывают каждого из рабочих закончить с одной машиной перед тем, как браться за другую.

% After preliminary investigation, Ben found out that the $i$-th
% car can be washed in $a_i$ minutes and cleaned in $b_i$ minutes.
% Washing and cleaning are performed at different buildings, so
% they cannot be performed simultaneously for the same car.
% The order of the two operations for a car is irrelevant, neither
% is the order of processing the cars. Ben's best workers Tom
% and Jerry were called to perform the order. Tom will wash the cars,
% and Jerry will dry-clean their compartments. 
% Each worker can work with one car at a moment, and due to
% quality requirements, it is not allowed to switch from one car to another
% until the one is ready (this condition is independent for each worker,
% different workers can process cars in any order).

\vspace*{0.5em}
Помогите Бену минимизировать время обработки заказа и составить расписание работ.
% Help Ben to find out
% how the cars should be processed by the workers,
% so that all cars were finished as soon as possible.

\InputFile

На первой строке число машин $n$ ($1 \le n \le 10\,000$).

Следующие $n$ строк содержат пары целых чисел $a_i$, $b_i$ ($1 \le a_i, b_i \le 10^5$).
% The first line of the input file contains $n$ ($1 \le n \le 10\,000$).
% The following $n$ lines contain two integer numbers each: $a_i$ and $b_i$
% ($1 \le a_i, b_i \le 10^5$).

\OutputFile

На первой строке выведите время выполнения заказа $t$.

% The first line of the output file must contain $t$ --- the number
% of minutes after the process has started when all cars will be 
% washed and dry-cleaned. You must minimize this number.

Следующие $n$ строк должны содержать по два числа -- когда Тому
начать мыть машину и когда Джери начать чистить её салон.
% The following $n$ lines must contain two integer numbers each ---
% the number of minutes after the start of the process when the
% washing and the dry-cleaning of the corresponding car must start,
% respectively.

Если есть несколько оптимальных расписаний, выведите любое.
% If there are several optimal solutions, output any one.

\Example

\begin{example}
\exmp{
6
10 6
7 9
3 8
1 2
12 7
6 6
}{
39
11 26
4 17
0 7
3 15
27 0
21 32
}%
\end{example}

\end{problem}

