3076 「2019 集训队互测 Day 3」公园

公园有 $n$ 个景点，$m$ 条连接两个景点的无向道路。第 $i$ 条道路连接第 $x_i$ 和第 $y_i$ 个景点。 若第 $i$ 条道路两端的景点主题相同，可以得到 $c_i$ 的美观度；若第 $i$ 条道路两端的景点主题不同，可以得到 $d_i$ 的美观度。 第 $i$ 个景点使用西部主题可以得到 $w_i$ 的美观度，使用科幻主题可以得到 $s_i$ 的美观度。 公园的线路图是小 Q 精心设计的，小 Q 保证她设计的公园中从任意一个景点出发，能够到达所有的景点；保证每条道路连接的是两个不同的景点；保证没有两条不同的道路连接同一对景点；并且对于任意四个景点 $A,B,C,D$ ，使得其中任意两条路径除公共端点外没有公共点，且这六条路径分别连接四个景点中的每一对景点—— $AB,AC,AD,BC,BD,CD$ 。 以下给出一些**一定不是**小 Q 设计的公园线路图的例子： || |:-:|:-:| |从 $1$ 号节点出发不能到达 $3$ 号节点|对于第 $1,4,5,6$ 号景点，存在六条两两没有公共边的路径：
$1\rightarrow4$，$4\rightarrow5$，$5\rightarrow6$，$6\rightarrow1$，$4\rightarrow3\rightarrow6$，$1\rightarrow2\rightarrow5$ 连接这四个景点的每一对景点| 你需要把每个景点的主题设定为科幻主题和西部主题中的一种，使得所有景点以及道路的美观度之和最大。 小 Q 可能会通过重新计算来修改某个景点的 $w_i$ 和 $s_i$ 的值或者某条道路的 $c_i$ 和 $d_i$ 的值。她会修改 $Q$ 次，你需要在修改之前以及每一次修改之后输出最优方案的美观度之和。注意修改与修改之间**不是**互相独立的。

第一行两个正整数 $n,m$ 。 接下来 $n$ 行，每行两个非负整数，其中第 $i$ 行表示 $w_i,s_i$ 。 接下来 $m$ 行，每行四个正整数，其中第 $i$ 行表示 $x_i,y_i,c_i,d_i$ 。 第 $n+m+2$ 行一个非负整数 $Q$ 。 接下来 $Q$ 行，每行三个正整数 $x,a,b$ ，若 $x \le n$ 则表示小Q把 $w_x$ 改为 $a$ ，把 $s_x$ 改为 $b$ ；若 $n < x \le n+m$ 则表示小Q把 $c_{x-n}$ 改为 $a$ ，把 $d_{x-n}$ 改为 $b$ 。

公园的线路图如图所示。 修改之前，最优方案为 $1$ 号景点使用西部主题，$2$ 号景点使用科幻主题，美观度之和为 $2+7+7=16$ 。 修改之后，最优方案为 $1$ 号景点使用科幻主题，$2$ 号景点使用科幻主题，美观度之和为 $6+7+5=18$ 。

保证 $2\le n \le 100000,Q \le 100000$；$x_i,y_i \le n$ ，$x \le n+m$ ，$s_i,w_i,c_i,d_i,a,b \le 10^6$。保证线路图是小Q设计的。

按照常理，公园是有出入口的。但是在本题中，你可以认为公园的出入口也是景点。

定义环路为起点和终点相同，并且中间（即除起点终点外）不经过重复景点的路径上道路的集合。

• 子任务 $1$（$2$ 分）：$Q=0$，$m=n-1$；
• 子任务 $2$（$3$ 分）：$n \le 17$，$Q\le 17$；
• 子任务 $3$（$7$ 分）：$Q=0$，每条道路最多属于一个环路；
• 子任务 $4$（$5$ 分）：$Q=0$；
• 子任务 $5$（$13$ 分）：$n,Q \le 1000$；
• 子任务 $6$（$19$ 分）：$s_i=w_i=0$，$x > n$，每条道路最多属于一个环路；
• 子任务 $7$（$17$ 分）：$s_i=w_i=0$，$x > n$；
• 子任务 $8$（$23$ 分）：$m=n-1$；
• 子任务 $9$（$11$ 分）：无特殊限制。