408537: GYM103182 F Secure documents

Alice has always dreamt about becoming a Security Software Engineer. She has recently been reading about how secure storage systems work. In one such system, there are documents and policies. Each document is tagged with a policy and policies are modelled as a DAG (Directed Acylic Graph). Each policy node may require a special key $$$k$$$ to access it. Additionally, access to a particular policy is dependant on access to all of its dependencies' policy.

Bob is a user of such system. Alice wants to determine at any given point the documents that Bob has access to. In particular, any document in the system is tagged with a policy and has a particular value - Alice wants to know the sum of values across the documents that Bob has access to.

Bob initially has zero keys. As time passes by, he gets access to different keys, which may unlock further access in the system for him. After every such new key, Alice needs to update her assessment of the sum of values across the documents Bob can see. Help her out with this task and she may return the favour in the future!

The first line of input will contain five integers: $$$ 1 \leq N \leq 2 \cdot 10^5$$$, $$$ 1 \leq M \leq 5 \cdot 10^5 $$$, $$$ 1 \leq D \leq 5 \cdot 10^5 $$$, $$$ 1 \leq K \leq 2 \cdot 10^5$$$, $$$ 1 \leq Q \leq 2 \cdot 10^5 $$$. $$$N$$$ is the total number of policy nodes in the system. $$$M$$$ is the number of dependencies between different policy nodes. $$$D$$$ is the total number of documents in the system. $$$K$$$ is the number of distinct keys that exist in the system. $$$Q$$$ is the number of queries that Alice has to answer to.

The next $$$M$$$ lines contain 2 integers each $$$x$$$ and $$$y$$$, meaning that access to policy $$$x$$$ requires access to policy $$$y$$$ first.

The next line contains $$$N$$$ numbers $$$p_i$$$ corresponding to the required key to access node $$$i$$$. If $$$p_i = -1$$$, that means no key is required to access node $$$i$$$. Where a key is required, it is guaranteed that $$$1 \leq p_i \leq K$$$.

The next $$$D$$$ lines contain a description of each document in the system. Each line has two values: $$$ 1 \leq policy_i \leq N$$$ and $$$0 \leq value_i \leq 10^9$$$.

The last $$$Q$$$ lines contain a key $$$1 \leq k_i \leq K$$$ Bob encounters over over time.

Print $$$Q$$$ lines. After each new key $$$k_i$$$, output the sum of documents' values Bob has access to. Note that he maintains access of all his previously found keys $$$k_j$$$ with $$$j \le i$$$.

4 1 6 4 4
3 1
-1 2 1 3
3 6
3 2
2 9
2 1
3 6
2 3
3
1
4
2

0
14
14
27