Built-in command queue
Embedded Command Queueing, also known as Native Command Queuing (NCQ), is a technology used in SATA devices to improve performance. NCQ allows a device to collect multiple requests and optimize their execution order based on the device's internal structure, aiming to reduce head movements and idle time while waiting for the desired sector on the track. In this task, we will focus solely on the time it takes for the SATA device's read/write head to move, ignoring other factors. Initially, assume the head is positioned at 0, moving at a speed of 1 position per millisecond. You are given commands in the format (x_i, t_i), where x_i is the position to read from or write to, and t_i is the time the request is received. Commands do not need to be processed in the order they arrive. The key requirement is that the device's head reaches position x_i at or after time t_i. The time taken for reading or writing is negligible. Your task is to determine the minimum time required to process all incoming commands.
Input
The first line of the input contains an integer n (1 ≤ n ≤ 2000), representing the number of commands received. The following lines contain the commands, each specified by a pair of integers x_i, t_i (-10^6 ≤ x_i ≤ 10^6; 0 ≤ t_i ≤ 10^6).
Output
Output a single number, which is the minimum time required to process all the commands.