女孩莉娜喜欢一切都井然有序,处处寻找秩序。有一次,她为上大学做准备,发现房间里一片狼藉——她手提包里的所有物品都被扔在房间里。当然,她想把它们放回手提包里。问题是女孩不能一次携带两个以上的物体,也不能移动手提包。而且,如果他拿走了一个物体,她就不能把它放在手提包之外的任何地方——她固有的秩序感不允许她这样做。
您将获得手提包的坐标以及某些笛卡尔坐标系中物体的坐标。众所周知,女孩所用的时间等于物体点之间线段长度的平方,从而走过任意两个物体之间的距离。据了解,最初女孩和手提包的坐标是相同的。你被要求找到这样一个动作顺序,即女孩可以在最短的时间内将所有物品放回她的手提包中。
输入
输入文件的第一行包含手提包的坐标 xs、ys。第二行包含数字 n (1 ≤ n ≤ 24) — 女孩拥有的物体数量。接下来的 n 行包含对象的坐标。所有坐标的绝对值不超过100。所有给定的位置都不同。所有数字都是整数。
输出
在第一行中输出唯一的数字——女孩将物品放入手提包所需的最短时间。
在第二行中输出 Lena 可能的最佳方式。输入中的每个对象都由其索引号(从 1 到 n)描述,手提包的点由数字 0 描述。路径应以手提包的点开始和结束。如果有多个最佳路径,则打印其中任何一个。
示例
输入 #1
0 0 2 1 1 -1 1
输出 #1
8 0 1 2 0
输入 #2
1 1 3 4 3 3 4 0 0
输出 #2
32 0 1 2 0 3 0