SP7378 MCOMP - Manhattan Companies

Everyone knows what Manhattan streets look like. For simplicity, we'll say there are two types of streets: horizontal and vertical (when seen on a map). For two junctions A and B, with coordinates (ax, ay), (bx, by) respectively, we define distance( A, B ) = |ax-bx| + |ay-by|. A company in Manhattan has the following problem: we have to link N junctions by couriers in such a way that each pair of junctions can communicate through the couriers. We must use the minimal possible number of couriers to do so. Also, of all the possible solutions with the minimal number of couriers, we'll take the one that minimizes the maximum distance of assigned junction pairs over all the couriers.

The first line of input contains a single integer: N (2

The first and only line of output should contain the minimal maximum distance over all the couriers defined above.