CF1184B3.The Doctor Meets Vader (Hard)

The rebels have saved enough gold to launch a full-scale attack. Now the situation is flipped, the rebels will send out the spaceships to attack the Empire bases!

The galaxy can be represented as an undirected graph with $n$ planets (nodes) and $m$ wormholes (edges), each connecting two planets.

A total of $s$ rebel spaceships and $b$ empire bases are located at different planets in the galaxy.

Each spaceship is given a location $x$, denoting the index of the planet on which it is located, an attacking strength $a$, a certain amount of fuel $f$, and a price to operate $p$.

Each base is given a location $x$, a defensive strength $d$, and a certain amount of gold $g$.

A spaceship can attack a base if both of these conditions hold:

• the spaceship's attacking strength is greater or equal than the defensive strength of the base
• the spaceship's fuel is greater or equal to the shortest distance, computed as the number of wormholes, between the spaceship's node and the base's node

The rebels are very proud fighters. So, if a spaceship cannot attack any base, no rebel pilot will accept to operate it.

If a spaceship is operated, the profit generated by that spaceship is equal to the gold of the base it attacks minus the price to operate the spaceship. Note that this might be negative. A spaceship that is operated will attack the base that maximizes its profit.

Darth Vader likes to appear rich at all times. Therefore, whenever a base is attacked and its gold stolen, he makes sure to immediately refill that base with gold.

Therefore, for the purposes of the rebels, multiple spaceships can attack the same base, in which case each spaceship will still receive all the gold of that base.

The rebels have tasked Heidi and the Doctor to decide which set of spaceships to operate in order to maximize the total profit.

However, as the war has been going on for a long time, the pilots have formed unbreakable bonds, and some of them refuse to operate spaceships if their friends are not also operating spaceships.

They have a list of $k$ dependencies of the form $s_1, s_2$, denoting that spaceship $s_1$ can be operated only if spaceship $s_2$ is also operated.

叛军已积攒了足够多的黄金，准备发动全面进攻！如今局势逆转，叛军将派出宇宙飞船攻击帝国基地！

银河系可被建模为一个无向图，其中包含 $n$ 颗行星（节点）和 $m$ 个虫洞（边），每条边连接两颗行星。

共有 $s$ 艘叛军宇宙飞船和 $b$ 座帝国基地，分别位于银河系中不同的行星上。

每艘宇宙飞船具有如下属性：位置 $x$（表示其所在行星的索引）、攻击力 $a$、燃料量 $f$，以及运行成本 $p$。

每座基地具有如下属性：位置 $x$、防御力 $d$，以及黄金储量 $g$。

一艘宇宙飞船能够攻击一座基地，当且仅当同时满足以下两个条件：

• 该飞船的攻击力不小于该基地的防御力；
• 该飞船的燃料量不小于该飞船所在节点到该基地所在节点之间的最短距离（以经过的虫洞数量计）。

叛军战士极为骄傲。因此，若一艘飞船无法攻击任何基地，则没有任何叛军飞行员愿意操作它。

若一艘飞船被操作，则其产生的利润等于其所攻击基地的黄金储量减去该飞船的运行成本。注意：该利润可能为负值。被操作的飞船将选择使其利润最大化的那座基地进行攻击。

达斯·维达始终希望展现自己的富有。因此，每当一座基地遭到攻击并被夺走黄金时，他都会立即用黄金将其重新填满。

因此，对叛军而言，多艘飞船可以攻击同一座基地；此时，每艘飞船仍能获得该基地的全部黄金。

叛军已委派海蒂（Heidi）与博士（the Doctor）决定应操作哪些飞船，以使总利润最大化。

然而，由于战争已持续良久，飞行员之间已结下牢不可破的情谊，部分飞行员拒绝操作飞船，除非他们的朋友也在操作飞船。

他们提供了一份包含 $k$ 个依赖关系的列表，每个依赖关系形如 $s_1, s_2$，表示：仅当飞船 $s_2$ 被操作时，飞船 $s_1$ 才可被操作。

The first line of input contains integers $n$ and $m$ ($1 \leq n \leq 100$, $0 \leq m \leq 10000$), the number of nodes and the number of edges, respectively.

The next $m$ lines contain integers $u$ and $v$ ($1 \leq u, v \leq n$) denoting an undirected edge between the two nodes.

The next line contains integers $s$, $b$ and $k$ ($1 \leq s, b \leq 10^5$, $0 \leq k \leq 1000$), the number of spaceships, bases, and dependencies, respectively.

The next $s$ lines contain integers $x, a, f, p$ ($1 \leq x \leq n$, $0 \leq a, f, p \leq 10^9$), denoting the location, attack, fuel, and price of the spaceship. Ships are numbered from $1$ to $s$.

The next $b$ lines contain integers $x, d, g$ ($1 \leq x \leq n$, $0 \leq d, g \leq 10^9$), denoting the location, defence, and gold of the base.

The next $k$ lines contain integers $s_1$ and $s_2$ ($1 \leq s_1, s_2 \leq s$), denoting a dependency of $s_1$ on $s_2$.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100$，$0 \leq m \leq 10000$），分别表示节点数和边数。

接下来的 $m$ 行每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示节点 $u$ 与节点 $v$ 之间存在一条无向边。

接下来的一行包含三个整数 $s$、$b$ 和 $k$（$1 \leq s, b \leq 10^5$，$0 \leq k \leq 1000$），分别表示飞船数量、基地数量和依赖关系数量。

接下来的 $s$ 行每行包含四个整数 $x$、$a$、$f$、$p$（$1 \leq x \leq n$，$0 \leq a, f, p \leq 10^9$），分别表示该飞船的位置、攻击力、燃料量和价格。飞船编号从 $1$ 到 $s$。

接下来的 $b$ 行每行包含三个整数 $x$、$d$、$g$（$1 \leq x \leq n$，$0 \leq d, g \leq 10^9$），分别表示该基地的位置、防御力和黄金数量。

接下来的 $k$ 行每行包含两个整数 $s_1$ 和 $s_2$（$1 \leq s_1, s_2 \leq s$），表示飞船 $s_1$ 依赖于飞船 $s_2$。

Print a single integer, the maximum total profit that can be achieved.

输出一个整数，表示能够获得的最大总利润。

The optimal strategy is to operate spaceships 1, 2, and 4, which will attack bases 1, 1, and 2, respectively.

最优策略是操作飞船 1、2 和 4，它们将分别攻击基地 1、1 和 2。