题目内容

某电力公司使用无人机对 $n$ 个电力塔进行巡检。每个电力塔 $i$ 位于坐标 $(x_i, y_i)$，无人机从基地（坐标 $(0,0)$）出发，需要依次飞达每个电力塔完成巡检后结束任务，无需返回基地。

无人机同一时刻只能飞向一个电力塔，请规划巡检顺序，使无人机飞行的总距离最短（两个坐标点间按曼哈顿距离计算，即 $|x_1-x_2| + |y_1-y_2|$），输出最短总距离。

输入描述

• $n$：电力塔数量，$1 \leq n \leq 15$
• $x_i, y_i$：第 $i$ 个电力塔的坐标，$0 \leq x_i, y_i \leq 200$

输出描述

输出最短总距离（整数）

样例1

输入

3,[[1,2],[3,1],[2,3]]

输出

8

说明

3 个电力塔：$A(1,2)$、$B(3,1)$、$C(2,3)$。基地为 $O(0,0)$。

• 巡检顺序 $A \to C \to B$：$O \to A$ 距离 $|1-0|+|2-0|=3$，$A \to C$ 距离 $|1-2|+|2-3|=2$，$C \to B$ 距离 $|2-3|+|3-1|=3$。总距离 $3+2+3=8$
• 巡检顺序 $A \to B \to C$：$O \to A$ 距离 $3$，$A \to B$ 距离 $|1-3|+|2-1|=3$，$B \to C$ 距离 $|3-2|+|1-3|=3$。总距离 $9$
• 巡检顺序 $B \to A \to C$：$O \to B$ 距离 $4$，$B \to A$ 距离 $3$，$A \to C$ 距离 $2$。总距离 $9$

其余顺序总距离均不小于 8，最短总距离为 8。

样例2

输入

2,[[1,1],[2,2]]

输出

4

说明

2 个电力塔：$A(1,1)$、$B(2,2)$。基地为 $O(0,0)$。

• 巡检顺序 $A \to B$：$O \to A$ 距离 $|0-1|+|0-1|=2$，$A \to B$ 距离 $|1-2|+|1-2|=2$。总距离 $2+2=4$
• 巡检顺序 $B \to A$：$O \to B$ 距离 $|0-2|+|0-2|=4$，$B \to A$ 距离 $|2-1|+|2-1|=2$。总距离 $4+2=6$

最短总距离为 4。