SF Round 5 暨 NOIP 信心赛

D. 解答题(response)

描述

注意：本场比赛每道题满分均为 100 分，提交显示 Accepted 不一定代表通过。

MuRongzhang 现在正在完成某道解答题，可是他没法一眼看出完整的解答过程，只能通过题目条件和一些定理来一步一步地推导。

这道题总共有 $N$ 个条件（编号为 $1 \sim N$ ）。起初，这 $N$ 个条件彼此之间都没有建立联系，并且这些条件上都没有建立模型（包括计算模型与图形模型）。现在已知这 $N$ 个条件都能建立模型，并且其中有 $M$ 对条件（编号为 $1 \sim M$ ）可以建立联系（这个联系是双向的）。

现在，MuRongzhang 正在做题。具体地，他可以进行任意次下列三种操作之一：

选择一个编号为 $i(1 \leq i \leq N)$ 的条件，建立计算模型。这需要花费他 $X_i$ 单位的时间。
选择一个编号为 $i(1 \leq i \leq N)$ 的条件，建立图形模型。这需要花费他 $Y_i$ 单位的时间。
在可以建立联系的 $M$ 对条件中选择编号为 $i(1 \leq i \leq M)$ 的一对（即条件 $A_i$ 与条件 $B_i$ ）建立联系。这需要花费他 $Z_i$ 单位的时间。

如果对于任意的两个条件 $i,j(1 \leq i,j \leq N,i \neq j)$ ，都能满足以下的三种情形之一，那么可以视作完成了这道解答题。

条件 $i,j$ 都建立了计算模型。
条件 $i,j$ 都建立了图形模型。
条件 $i,j$ 之间建立了联系（两个条件是可以间接建立联系的，比如如果条件 $1,2$ 和条件 $2,3$ 之间分别建立联系，那么可以视作条件 $1,3$ 之间建立了联系）。

请问， MuRongzhang 最少需要花费总共多少个单位的时间才能完成这道解答题？

输入

本题输入规模较大，请使用较快的输入输出方式。

输入共 $M + 3$ 行。

第一行两个非负整数 $N,M$ ，含义见题目描述。

第二行 $N$ 个正整数 $X_1,X_2,\cdots,X_n$ ，含义见题目描述。

第三行 $N$ 个正整数 $Y_1,Y_2,\cdots,Y_n$ ，含义见题目描述。

接下来 $M$ 行，其中的第 $i$ 行为三个正整数 $A_i,B_i,Z_i$ ，含义见题目描述。对于任意 $1 \leq i < j \leq N$ ， $A_i = A_j$ 和 $B_i = B_j$ 不同时成立，并且 $A_i \neq B_i$ 。

输出

一行一个非负整数，为 MuRongzhang 完成这道解答题最少需要花费的总时间。

样例

输入

输出

输入

输出

输入

8 13
78 17 52 88 22 19 61 87
22 55 34 100 45 12 32 100
1 2 80
1 4 10
1 5 24
2 3 62
2 4 68
3 5 81
3 6 3
3 7 8
3 8 49
4 6 74
4 4 32
5 8 36
5 5 10

输出

提示

样例解释

样例1

在 $1,3$ 号条件上建立计算模型（分别花费 $1,4$ 个单位时间），在 $2,4$ 号条件上建立图形模型（分别花费 $2,3$ 个单位时间），在 $1,4$ 号条件之间建立联系（花费 $6$ 个单位时间），总共耗费 $16$ 个单位时间。

样例2

直接在 $1,2,3$ 号条件上建立计算模型即可。计算模型与图形模型都不要求强制建立。

数据范围

对于 $15\%$ 的数据， $N \leq 8$ ， $M \leq 15$ 。

对于 $30\%$ 的数据， $N \leq 5 \times 10^3$ 。

另有 $5\%$ 的数据， $M=0$ 。

另有 $10\%$ 的数据， $5 \times 10^3$ ，具有特殊性质 A。

另有 $15\%$ 的数据， $5 \times 10^3$ ，具有特殊性质 B。

对于所有数据， $2 \leq N \leq 2 \times 10^5$ ， $0 \leq M \leq 2 \times 10^5$ ， $1 \leq X_i,Y_i,Z_i \leq 10^9$ ， $1 \leq A_i , B_i \leq N$ 。

特殊性质 A： $X_i=Y_i=10^9,1 \leq Z_i < 5 \times 10^3$

特殊性质 B： 令 $C_i$ 为满足 $A_k = i$ 或 $B_k = i(1 \leq k \leq M)$ 的 $k$ 的个数，则对于 $1 \leq i \leq N$ 的正整数 $i$ ，满足 $C_i = 1$ 的有且只有 $2$ 个，满足 $C_i = 2$ 的有且只有 $N-2$ 个。

Submit

时间限制	2 秒
内存限制	128 MB

提交