A Home for Chef

Our hardworking chef is bored of sleeping in his restaurants. He has decided to settle down. The first thing he must do is to find a suitable location to build a palatial home. Think of the city as a two-dimensional grid. There are N restaurants in the city. Each of the chef's restaurant is a point denoted by (X , Y). A house can be located at a grid point (R, S) if the sum of the distances betwe