Вбудована черга команд
Вбудована черга команд (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).
Вихідні дані
Виведіть єдине число — найменший час обробки всіх команд.