Встроенная очередь команд
Встроенная очередь команд (Native Command Queuing, NCQ) - это технология, использующаяся в SATA-устройствах для повышения быстродействия. NCQ позволяет устройству накапливать запросы, оптимизировать порядок их выполнения с учётом внутренней архитектуры устройства (минимизация количества перемещений головок, простоя в ожидании нужного сектора на треке). В этой задаче мы пренебрежем значением ряда факторов и будем учитывать только лишь время перемещения считывающей головки SATA-устройства. Изначально будем считать, что головка расположена в позиции 0. Скорость ее перемещения равна 1 (одна позиция в миллисекунду). Вам заданы команды в виде (x_i, t_i), где x_i – позиция из которой надо прочесть (или записать) информацию, а t_i – время поступления запроса. Запросы не обязательно должны быть обработаны в порядке их поступления. Главное, чтобы головка устройства заняла позицию x_i в момент времени t_i или позже. Время чтения/записи будем считать пренебрежимо малым. Найдите наименьшее время, за которое устройство обработает все поступившие команды.
Входные данные
В первой строке входного файла записано целое число n (1 ≤ n ≤ 2000) – количество поступивших команд. Далее перечислены сами команды – по одной в строке. Команды задаются парами целых чисел x_i, t_i_{ }(-10^6 ≤ x_i ≤ 10^6; 0 ≤ t_i ≤ 10^6).
Выходные данные
Выведите единственное число – наименьшее время обработки всех команд.