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