题目描述

贝尔兰正在发生内战，这一次似乎已经很难通过和平方式解决问题，国家分裂为东贝尔兰和西贝尔兰几乎不可避免。

灰军总司令 Kruglyakovski 将军决定加快这一进程，并在自己的司令部周围修建一道围墙——后来它将被称为“伟大的贝尔兰墙”。围墙必须使敌方司令部位于围墙的另一侧，也就是说，两座司令部必须被围墙分隔开。

观察贝尔兰地图后，将军发现，整个国家由若干个省份组成。每个省份都是一个简单多边形，但不一定是凸多边形。

贝尔兰不存在飞地，也不存在其他国家位于贝尔兰内部的飞地。换句话说，从贝尔兰中的任意一点都可以在始终不离开贝尔兰的情况下到达另一点。

对于每一段省界，都给定了一个“通行性”数值。原题中，这个数值表示士兵沿该边界线段移动时所允许的最大速度。

Kruglyakovski 将军规定：

• 围墙只能沿省份之间已有的边界线段修建；
• 整道围墙必须构成一个简单多边形；
• 将军自己的司令部和敌方司令部必须位于围墙的不同侧。

士兵将在夜间修建围墙。修建某一段围墙所需要的时间，数值上等于对应省界线段给出的“通行性” $v$；整道围墙的修建时间等于其所有组成线段的修建时间之和。

请找到一种满足要求的围墙，使总修建时间最小，并输出一种最优方案。

输入格式

第一行包含一个整数 $N$，表示所有省界线段的数量：

$5\le N\le300$。

接下来 $N$ 行，每行包含五个整数：

$x_1\ y_1\ x_2\ y_2\ v$

表示一条省界线段，其两个端点分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$，其“通行性”为 $v$。

满足：

• $1\le v\le1000$；
• 任意两条线段至多有一个公共点；
• 如果两条线段存在公共点，那么这个公共点只能同时是两条线段的端点。

最后一行包含四个整数：

$X_1\ Y_1\ X_2\ Y_2$

其中 $(X_1,Y_1)$ 是 Kruglyakovski 将军司令部的位置，$(X_2,Y_2)$ 是敌方司令部的位置。

两座司令部都严格位于某个省份的内部，并且位于不同的省份中。

输入中所有坐标均为整数，且绝对值小于 $10^4$。

输出格式

第一行输出一个整数，表示修建最优围墙所需的最小总时间。

第二行输出一个整数 $K$，表示围墙使用的省界线段数量。

第三行输出 $K$ 个整数，表示这些线段的编号，按照围墙上的顺序给出。

输入中的省界线段按照出现顺序从 $1$ 到 $N$ 编号。

如果存在多个最优方案，可以输出任意一个。

样例

13
0 6 3 6 9
0 0 4 2 8
4 4 6 6 7
2 4 3 6 1
3 6 6 6 1
6 4 6 6 1
4 2 6 4 1
0 0 0 6 6
2 2 2 4 1
2 2 4 2 1
0 6 2 4 5
2 4 4 4 4
4 2 4 4 3
3 3 2 5

6
6
9 10 4 7 5 6