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.

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$ .

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.