Вбудована черга команд#2090
Вбудоване чергування команд (Native Command Queuing, NCQ) — це технологія, яка використовується в SATA-пристроях для підвищення продуктивності. NCQ дозволяє пристрою накопичувати запити та оптимізувати порядок їх виконання відповідно до внутрішньої структури пристрою, зменшуючи переміщення головки та час простою під час очікування потрібного сектора на доріжці. У цьому завданні ми не враховуватимемо деякі фактори й розглядатимемо лише час, необхідний для переміщення зчитувальної/записувальної головки SATA-пристрою. Спочатку вважатимемо, що головка знаходиться у позиції і рухається зі швидкістю позиція за мілісекунду. Вам дано команди у форматі (x_i, t_i), де x_i — позиція для зчитування чи запису, а t_i — час надходження запиту. Команди не обов'язково обробляти в тому порядку, в якому вони надходять. Основна вимога полягає в тому, що головка пристрою має досягти позиції x_i не раніше часу t_i (тобто в момент часу t_i або пізніше). Час на операцію зчитування або запису вважається нескінченно малим. Знайдіть мінімальний час, необхідний для обробки всіх команд.
Перший рядок містить одне ціле число (1 \le n \le 2000) — кількість вхідних команд. Наступні рядків містять команди, кожна у вигляді пари цілих чисел x_i, t_i (-10^6 \le x_i \le 10^6; 0 \le t_i \le 10^6).
Виведіть одне число — мінімальний час, необхідний для виконання всіх команд.
Приклад 1