附耳而至

题目背景

Enchanters, remind

That time will not unwind,

The dragon's crooked spine

Will never straighten into line.

题目描述

小X的妹妹小L是一名X国的占卜师。

占卜的工作往往要通过一些仪式来完成，这一次，小L仪式的场地就是一个「星座」。一个「星座」由$N$颗「星」和$M$条「星路」组成，每一颗「星」有一个属于自己的坐标$(x_i,y_i)$和代表「光明」和「黑暗」的两个数值$a_i,b_i$，一条「星路」以线段的方式连接一对「星」，并具有一个代表其「代价」的数值$c_i$。为了保证「星座」不会紊乱，任意一对「星路」不会在其中任意一条「星路」的非顶点处存在公共点，并且，任意一颗「星」都可以通过「星路」到达其余所有「星」。

可以发现，「星」和「星路」将平面分割成了若干个区域，其中包括一个无穷大的区域。「星座」的性质还保证了，一个非无穷大的区域一定是由「星」为顶点，「星路」为边的一个简单多边形，所有非无穷大的区域的并也是一个简单多边形。 一个非无穷大的区域的「光明值」即为所有作为它的顶点的「星」的「光明值」$a_i$之和，而它的「黑暗值」即为所有作为它的顶点的「星」的「黑暗值」$b_i$之和，而无穷大的区域的「光明值」和「黑暗值」则是所有作为它补集的顶点的「星」对应的「光明值」和「黑暗值」之和。

在占卜的过程中，一个区域或将被「光明之神」选中，其「光明值」将加入X国的「气运」中；或将被「黑暗之神」选中，其「黑暗值」将加入X国的「气运」中。而共享一条「星路」的两个区域若同时被「光明之神」和「黑暗之神」选中，这条「星路」的「代价」$c_i$将会被从X国的「气运」中扣除。

作为占卜师，小L自然希望X国的「气运」能够被最大化，请帮助小L计算这个最大的「气运」值。

输入格式

第一行一个整数$Num$，表示测试点编号，以便选手方便地获得部分分，你可能不需要用到这则信息，样例中$Num$的含义为数据范围与某个测试点相同。

接下来一行两个整数$N,M$，分别表示「星座」中「星」和「星路」的数量。

接下来$N$行，每行四个整数$x_i,y_i,a_i,b_i$，分别一条颗「星」的坐标，以及其「光明值」和「黑暗值」。

接下来$M$行，每行三个整数$u_i,v_i,c_i$，表示一条连接第$u_i,v_i$颗「星」，「代价值」为$c_i$的「星路」。

输出格式

输出一行一个整数$Ans$，表示X国「气运」的最大值。

样例1输入

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

样例1输出

57

样例1解释

样例中的「星座」如下图所示：

使得X国的「气运」最大情况下，「光明之神」选中了三角形ABC和正方形ABDC的补集，即一个无穷大的区域，「黑暗之神」选中了三角形BCD。

此时，X国的「气运」为三角形ABC的「光明值」(20)、三角形BCD的「黑暗值」(20)、正方形ABDC的补集的「光明值」(20)之和减去「星路」BC,BD,CD的「代价值」之和(3)，即57。

样例2

见下发文件ex_everfeel2.in，ex_everfeel2.out

样例3

见下发文件ex_everfeel3.in，ex_everfeel3.out

点此下载

数据范围与约定

记「星座」的区域数为$C$。

对于所有测试数据，保证$1\leq N,C\leq 4\times 10^4$，$1\leq M\leq 2\times 10^5$。

$0\leq a_i,b_i\leq 10^3$，$0\leq c_i\leq 10^6$，$|x_i|,|y_i|\leq 2\times10^4$，$1\leq u_i,v_i\leq N$。

「星」的位置两两不同，一条「星路」两侧的区域互不相同。

详细的数据范围见下表。

一个「星座」是「弱网格图」，当且仅当$N$是完全平方数，且对于任意整数$i,j\ (1\leq i,j\leq \sqrt{N})$，$(i,j)$处均存在一颗「星」；每一条「星路」连接的两颗「星」的距离恰好是1。

一个「星座」是「网格图」，当且仅当它是「弱网格图」，且每一条可能出现的「星路」都存在。