It is clear that the path with the least number of returns is needed to be found. If in the final path, there exists a return from some village ~A~ to village ~B~, then that interval is visited three times (once more moving from ~B~ to ~A~). Without returning, that interval would be visited only once. So, intervals of returning are visited two more times and the final solution will be:

$$\displaystyle M + 2 \times (\text{complete length of returning intervals})$$

The goal is to find as short intervals of returning as possible. Persons that are traveling from left to right can be discarded: they will be transported in any case. Persons that are traveling from right to left are problematic: every one of them defines an interval of returning (but maybe just as part of another longer interval).

Now, the following solution is natural: we'll find the union of every interval of returning (defined by persons that go from right to left) and that union will be the complete length of intervals we are returning by.

The final goal is to find the union of given intervals very fast. This can be achieved using a "sweep line" algorithm: moving from left to right we register events "start of interval" and "end of interval". Complexity is ~\mathcal O(N \log N)~ for sorting.