548. Minimum Total Distance Traveled

Robots and factories lie on a number line. Each factory has a position and a repair limit (the maximum robots it can repair). Each robot must travel to some factory; the cost is the absolute distance. Assign every robot to a factory respecting limits so the total distance traveled is minimized, and return that minimum. The input is JSON {robots, factories} where factories is a list of [position, limit].

Input: JSON {robots, factories}.

Output: Integer — the minimum total distance.

Examples

Input: {"robots":[0,4,6],"factories":[[2,2],[6,2]]}
Output: 4
Explanation: Optimal assignment totals 4.

Input: {"robots":[1,-1],"factories":[[-2,1],[2,1]]}
Output: 2
Explanation: Each robot to the nearer factory.

Input: {"robots":[0],"factories":[[5,1]]}
Output: 5
Explanation: Single robot travels 5.

Constraints

• 1<=robots<=100
• 1<=factories<=100
• sum of limits >= robots

Asked by