Minimum Energy for Tree Cutting

You are given N trees located on a 2D grid. Each tree is represented by its coordinates \( (x, y) \). Starting from the first tree (index 0), you must determine the minimum energy required to cut down all of the trees and return to the starting tree.

The energy required to move between any two trees is equal to the Manhattan distance, defined by the formula:

\( D((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2| \)

Your goal is to find a route that starts at tree 0, visits every other tree exactly once, and returns to tree 0 with the minimum possible total energy cost.

Note: It is assumed that the number of trees is small (e.g., \( N \leq 10 \)) due to the computational complexity of evaluating all possible orders.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer ( N ) representing the number of trees. Each of the following ( N ) lines contains two space-separated integers representing the x and y coordinates of a tree.

outputFormat

Output a single integer to standard output (stdout) representing the minimum energy required to cut down all trees and return to the starting tree.## sample

3
0 0
1 0
0 1

4