Migrated from Lutece 2604 图像分割

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出一个 $n$ 个点，$m$ 条边的连通无向图，你需要给每个点染上两种颜色中的一种，不能不染。

若编号为 $i$ 的点被染成 $A$ 色，你可以获得价值 $A_i$ 的分数，若被染上 $B$ 色则获得 $B_i$ 的分数。

对于编号为 $j$ 的边，若它的两个端点颜色不同，则你会被扣除价值 $w_j$ 的分数。

求你能获得的最大的最终分数。

Input

第一行两个数，分别为点数 $n$ 和边数 $m$。

接下来一行 $n$ 个数，第 $i$ 个数为 $A_i$。

再接下来一行 $n$ 个数，第 $i$ 个数为 $B_i$。

接下来 $m$ 行，每行三个数 $u,v,w$，表示边的两个端点 $u,v$ 和这条边对应的价值 $w$。

Output

输出一个数表示答案。

Samples

7 11
705698 598721 559214 654137 511975 508730 844971
683515 920366 670141 740061 640839 896312 616508
1 2 60
1 3 65
1 6 69
1 5 17
1 4 34
2 6 78
3 4 52
3 5 19
4 7 44
4 6 9
6 7 33

5418066

Constraints

$2 \leqslant n \leqslant 200$，$1 \leqslant m \leqslant 5000$ $500001 \leqslant a_i \leqslant 1000000$，$500001 \leqslant b_i \leqslant 1000000$。 $1 \leqslant w \leqslant 100$ 保证不出现重边和自环。

Resources

2021 UESTC ICPC Training for Graph