Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

flows

shortest paths

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
B3. The Doctor Meets Vader (Hard)

time limit per test

4 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputThe 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.

Input

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

Output

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

Example

Input

6 7 1 2 2 3 3 4 4 6 6 5 4 4 3 6 4 2 2 1 10 2 5 3 8 2 7 5 1 0 2 6 5 4 1 3 7 6 5 2 3 4 2 3 2

Output

2

Note

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2024 21:34:06 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|