Each of Mirko's friends is described by numbers ~X, Y, P~. Notice that possible meeting points with a given friend form a square centered at ~(X, Y)~ – more precisely, a square with opposing vertices at ~(X-P, Y-P)~ and ~(X+P, Y+P)~.

Now the task has been reduced to finding the shortest possible path that touches all squares in order from first to last.

For each ~K~ from ~1~ to ~N~, we consider all possible shortest paths that visit squares ~1, 2, \dots, K~, in that order. Let ~S(K)~ be the set of all endpoints of those paths, i.e. the set of all positions where we could have ended up after visiting the first ~K~ friends in an optimal manner. Let ~d(K)~ be the length of these shortest paths.

Notice that ~S(1)~ is precisely the square corresponding to the first friend, since we could have started (and ended) a path with length ~0~ by visiting the first friend in any point of that square.

The solution should proceed to find ~S(2), S(3), \dots, S(N)~. As we will show, all the sets will be rectangles. Now we have to determine how to find ~S(K+1)~ if we are given ~S(K)~.

Let ~D~ be the minimum distance (number of steps) from any point of ~S(K)~ to the square belonging to the ~(K+1)^\text{st}~ friend (whom we need to visit next). Notice that ~d(K+1) = d(K)+D~.

If we expand the rectangle ~S(K)~ by ~D~ units in all four directions, we will obtain all points reachable after optimally visiting the first ~K~ friends and then moving ~D~ steps in any direction. The intersection of the expanded rectangle and the square corresponding to the ~(K+1)^\text{st}~ friend is therefore the set of points where we can meet friend ~K+1~ after making ~d(K)+D~ steps (from the definition of ~D~, the intersection is guaranteed to be nonempty) – therefore, this intersection is exactly ~S(K+1)~, furthermore it is a rectangle (as an intersection of a square and a rectangle, both aligned with the same axes).

The final solution is simply the sum of all ~D~ values obtained while finding ~S(2), S(3), \dots, S(N)~ – this is precisely ~d(N)~.