On a 2D grid you have N workers and M bikes (N <= M). Assign each worker exactly one unique bike so that the sum of Manhattan distances between each worker and the bike they are assigned to is as small as possible. Return that minimum sum.
The Manhattan distance between two points p and q is |p.x - q.x| + |p.y - q.y|.
Input
workers: array of [x, y] coordinates, one per worker
bikes: array of [x, y] coordinates, one per bike
Output
The minimum possible total Manhattan distance over all valid assignments.
Examples
Example 1
Inputworkers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output6
Example 2
Inputworkers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output4
Constraints
1 <= workers.length <= bikes.length <= 10
0 <= coordinate values < 1000
All worker and bike locations are distinct.