战争与和平

很久以前，华夏大地上有两位帝王 MJW 和 CRX。为了证明自己才是这片土地的主宰，他们发动了无数次战争。战争满足了两位帝王的野心，却也给这片土地带来了无穷的灾难。

MJW 在战争中屡次失利，逐渐失去了继续争霸的信心。为了阻止 CRX 再次发动战争，他决定修建城墙，将两人的首都完全隔离。

华夏大地由许多州组成。在平面地图上，每个州都是一个简单多边形。越过一个州的边界后，要么进入另一个州，要么离开华夏大地。任意两条边界要么完全重合，要么没有公共部分，要么仅在端点处相交，并且不存在一个州包含另一个州的情况。

MJW 和 CRX 的首都分别严格位于两个不同州的内部，且均不在任何边界上。修建的城墙必须将其中一人的首都包围起来，从而使两座首都完全隔离。

为了避免引起民众不满，城墙不能修建在州的内部，只能沿州的边界修建。如果选择在某条边界上修建城墙，就必须修建完整的整条边界，不能只修建其中一部分。

在不同边界上修建城墙需要支付不同的费用。请计算使两座首都完全隔离所需的最小总代价。

输入格式

第一行包含一个整数 $m$ ，表示不同边界的数量。

接下来给出 $m$ 组边界数据，每组包含 $5$ 个整数 $x_1,y_1,x_2,y_2,V$ ，表示该边界的两个端点分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$ ，沿这条边界修建城墙的代价为 $V$ 。

最后给出 $4$ 个整数 $m_x,m_y,c_x,c_y$ ，表示 MJW 的首都位于 $(m_x,m_y)$ ，CRX 的首都位于 $(c_x,c_y)$ 。

保证两座首都分别严格位于两个不同州的内部，且均不在任何边界上。

输出一个整数，表示使两座首都完全隔离所需的最小代价。

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

本题题面与测试数据整理自 BZOJ。

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