当前没有测试数据。

题目背景

IOI 2025 中国国家队选拔 d2t1。

题目描述

定义一个无自环、无重边的无向连通图是仙人掌图，当且仅当其任意一条边至多属于一个简单环，其中简单环指不经过重复结点的环。

给定平面上的 $n$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$。给定 $m$ 条边，第 $i$ 条边连接结点 $u_i, v_i$。保证由这 $n$ 个点与 $m$ 条边构成的无向图为仙人掌图。

初始时，所有的 $m$ 条边都是白色的。你可以选择若干条边，并将其染成黑色，其中将第 $i$ 条边染成黑色的代价为 $w_i$。对于每对有公共结点的异色边，设从白色边开始沿公共结点逆时针转 $x$ 条边可以到达黑色边，那么可以获得 $p\times x$ 的能量。特别地，对于两条共线且方向相同的边（即另一结点关于公共结点的极角相同的边），规定先到达编号较小的边，也即，编号较小的边的极角更小。

求染色后可以获得的能量总和减去染色代价总和的最大值。

输入格式

输入的第一行三个正整数 $n, m, p$，分别表示结点个数、边数、以及获得能量的系数。

接下来 $m$ 行，第 $i$ 行三个整数 $u_i, v_i, w_i$，表示第 $i$ 条边的结点与代价。

接下来 $n$ 行，第 $i$ 行两个整数 $x_i, y_i$，表示第 $i$ 个点的坐标。

输出格式

输出一行一个整数，表示染色后可以获得的能量总和减去染色代价总和的最大值。

输入输出样例 #1

输入 #1

5 4 10
1 4 1
2 3 2
3 4 2
3 5 2
0 1
1 1
0 0
1 0
2 0

输出 #1

38

输入输出样例 #2

输入 #2

见附件

输出 #2

见附件

说明/提示

样例解释

样例 $1$ 解释

如下图所示，黑色实线表示被染成黑色的边，灰色点线表示仍为白色的边。

花费 $2$ 的代价将 $(3, 4)$ 染为黑色后，从 $(1, 4)$ 沿结点 $4$ 逆时针转 $1$ 条边可以到达 $(3, 4)$，获得 $10 \times 1 = 10$ 能量；从 $(2, 3)$ 沿结点 $3$ 逆时针转 $1$ 条边可以到达 $(3, 4)$（注意：根据题目描述中的规定，会先到达 $(3, 4)$ 后到达 $(3, 5)$），获得 $10 \times 1 = 10$ 能量；从 $(3, 5)$ 沿结点 $3$ 逆时针转 $2$ 条边可以到达 $(3, 4)$，获得 $10 \times 2 = 20$ 能量。因此染色后可以获得的能量总和为 $10 + 10 + 20 = 40$，代价总和为 $2$，所求的最大值为 $40 − 2 = 38$。

可以证明，不存在答案更大的染色方案。

数据范围

对于所有测试数据，保证

• $2 \le n, m \le 2 \times 10^5$，$1 \le p \le 1000$，
• $\forall 1 \le i \le m, 1 \le u_i, v_i \le n, 0 \le w_i \le 10^4$，
• $\forall 1 \le i \le n, 0 \le x_i, y_i \le 10^7$，
• 给定的图是仙人掌图；
• 任意两个点坐标不重合。

子任务编号	分值	$n,m\le$	特殊性质
$1$	$7$	$20$	AB
$2$	$9$		无
$3$		$8,000$	AB
$4$	$9$		A
$5$	$30$		无
$6$	$11$	$2\times 10^5$	A
$7$	$1$		C
$8$	$12$		D
$9$	$18$		无

• 特殊性质 A：保证 $m = n − 1$，也即给定的图是一棵树。
• 特殊性质 B：保证给定的图上任意一对没有公共结点的边在平面上不相交，也即给定的图是平面嵌入。
• 特殊性质 C：保证 $\forall 1 \le i \le m, w_i = 0$。
• 特殊性质 D：保证 $\forall 1 \le i \le m, w_i = 1$，$p = 1$。