Base Stations

A wireless carrier wants to install base stations on a straight communication line so that every important building in the plane lies inside at least one coverage area.

The communication line is the x-axis. Each base station is installed at a point on this line. Its coverage area is a square centered at the station, with sides parallel to the coordinate axes. The side length of this square is called the station's communication width.

The total installation cost is the sum of the communication widths of all installed stations; the number of stations itself does not add any cost.

Given the coordinates of all important buildings, find the minimum possible total installation cost needed to cover every building. Building coordinates are integers, no building lies on the communication line, and all building positions are distinct.

The first line contains the number of buildings N. (1 <= N <= 10,000)

Each of the next N lines contains two integers, the x-coordinate and y-coordinate of one building, separated by a space. Each coordinate has absolute value at most 1,000,000.

Print the minimum possible total installation cost: the minimum sum of communication widths over all installed base stations.