Built-in command queue#2090
Embedded Command Queueing (Native Command Queuing, NCQ) is a technology used in SATA devices to improve performance. NCQ allows the device to collect requests and optimize their execution order based on the device's internal structure, reducing head movements and idle time while waiting for the desired sector on the track. In this task, we will disregard some factors and consider only the time it takes for the SATA device's read/write head to move. Initially, assume the head is at position , moving at a speed of 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 arrives. The commands do not have to be processed in the order they are received. The main requirement is that the device's head reaches position x_i at time t_i or later. The time for reading or writing is considered negligible. Find the minimum time required to process all commands.
The first line contains an integer (1 \le n \le 2000), the number of incoming commands. The next lines contain the commands, each given as a pair of integers x_i, t_i (-10^6 \le x_i \le 10^6; 0 \le t_i \le 10^6).
Output a single number: the minimum time needed to process all the commands.
Example 1