Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). A teleporter is described by two numbers xx and yy, where manure brought to location xx can be instantly transported to location yy.
Farmer John decides to build a teleporter with the first endpoint located at x=0x=0; your task is to help him determine the best choice for the other endpoint y. In particular, there are NN piles of manure on his farm (1≤N≤100,0001≤N≤100,000). The iith pile needs to moved from position aiai to position bi, and Farmer John transports each pile separately from the others. If we let didi denote the amount of distance FJ drives with manure in his tractor hauling the ith pile, then it is possible that di=|ai−bi|di=|ai−bi| if he hauls the ith pile directly with the tractor, or that didi could potentially be less if he uses the teleporter (e.g., by hauling with his tractor from aiai to xx, then from yy to bibi).
Please help FJ determine the minimum possible sum of the didi's he can achieve by building the other endpoint yy of the teleporter in a carefully-chosen optimal position. The same position yy is used during transport of every pile.
3 -5 -7 -3 10 -2 7
10
In this example, by setting y=8 FJ can achieve d1=2, d2=5, and d3=3. Note that any value of yy in the range [7,10] would also yield an optimal solution.
3
-5 -7
-3 10
-2 7
10