Gathering Cats: Minimizing Manhattan Moves

You are given N cats each located at a feeding station on a 2D grid. Each feeding station is located at coordinates \( (x_i, y_i) \). Although each station has an associated food quantity \( f_i \), this value is irrelevant to the number of moves. A move is defined as a unit Manhattan distance (i.e., moving one unit north, south, east, or west).

Your task is to determine the minimum number of moves required to gather all cats at a single feeding station. It is known that the optimal meeting point (minimizing the total Manhattan distance) is achieved by choosing the median of the x-coordinates and the median of the y-coordinates. In other words, if \( x_{med} \) and \( y_{med} \) are the medians, the minimum total move is given by:

[ \text{total y distance} = \sum_{i=1}^{N} \left(|x_i - x_{med}| + |y_i - y_{med}|\right) ]

Note: When \( N \) is even, choosing any value between the two middle elements will yield the optimal solution. In this problem, you can select the \( \lceil N/2 \rceil \)-th smallest coordinate as the median.

inputFormat

The input is given via standard input (stdin) and consists of:

1. The first line contains an integer \( N \) representing the number of cats (and feeding stations).
2. Each of the next \( N \) lines contains three space-separated integers \( x_i \), \( y_i \), and \( f_i \) where \( (x_i, y_i) \) are the coordinates of a feeding station and \( f_i \) is the food amount (which can be ignored).

outputFormat

Output a single integer to standard output (stdout) representing the minimum total number of moves required to gather all the cats at one feeding station.

3
1 1 2
1 3 3
3 3 1

4