Far far away, in an alien galaxy, M friends decide to meet up and play the "Exploding Kittens" game. They all agreed upon how to pick the meetup location: they will all show up at the house of the alien friend which lives closest to everyone else.
Their world is not like the 3D space we are used to, because it has N dimensions. They all live at integer coordinates in their world, meaning that a house location is an N-dimensional vector of the form (x1, x2, …, xn), where x1, x2, …, xn are all integers. At any time, an alien can move from one position to another only if exactly one of the vector's components changes by 1 unit in absolute value. For example, in a 2D space, from a given position he can only move to the North, West, South or East directions in one step.
Your task is to compute the minimal number of steps needed for all friends to get to the meeting point. This will be a SUM(di), where di represents the minimal number of steps needed for the i-th friend to arrive at the meeting place, starting from his house. In addition to this, you should print the number of friends whose houses satisfy this minimal distance requirement and their houses' coordinates, in lexicographical order.
The first line of input contains integers M and N, separated by a space.
Each of the following M lines contains N integers, representing the coordinates of a house.
The first line of the output should contain the minimum total meeting distance, as described in the statement.
The next line should contain the number of houses H for which the total meeting distance is minimal. The next H lines should contain the coordinates of these houses. The houses should be sorted lexicographically.
- 1 ≤ M ≤ 50000
- 1 ≤ N ≤ 25
- 1 ≤ N * M ≤ 250000
- 10-9 ≤ xij ≤ 109, where xij is the jth coordinate of the ith house
We first observe that the problem is independent for each dimension.
Therefore we should solve the problem in a 1 dimensional space and the same principle applies to all dimensions.
For the 1D problem, we sort the elements in ascending order of the (only) coordinate and then we can use partial sums to the left and to the right to compute the manhattan distance from one point to all the others in O(M) in total. We just need to take care that we add the manhattan distance to the correct initial point (as the order may differ when sorting on different axis).
Therefore the algorithm is O(N * M * logM) orO(N * M) using the integer property of coordinates and radix / bucket sort.