Background

As various forces moved in, Moriya Shrine lost quite a lot of faith.

Now, in order to bring back the shrine’s increasingly declining incense offerings, Yasaka Kanako sends the shrine’s wind priestess Sanae to the Human Village to collect faith.

Problem Description

You can view the village as a directed acyclic graph (DAG) with $m$ nodes. On some nodes there are $n$ clusters of faith to be collected (each cluster has a certain amount). The graph has $k$ directed edges, and each edge has length $1$.

Sanae will start from node $1$ and may stop collecting at any node in the graph. When Sanae is at a node that has faith, she will collect all the faith on that node (including node $1$).

For convenience, Sanae learned teleportation from Usami Sumireko, so she can move $a$ units of length at a time (called a small teleport), or move $b$ units of length at a time (called a big teleport). These cost $w_a$ and $w_b$ spirit power respectively. It is guaranteed that $a \le b$, but since Gensokyo is not bound by common sense, $w_a$ is not necessarily less than $w_b$.

Now, Sanae wants you to help her find the maximum possible value of (amount of faith collected $-$ spirit power cost) she can obtain in the village.

Input Format

The first line contains three integers $n,m,k$, representing the number of nodes with faith, the total number of nodes, and the number of directed edges.

The second line contains two integers $a,b$, representing the distances of the two types of teleport.

The third line contains two integers $w_a,w_b$, representing the spirit power costs of the two types of teleport.

Then $n$ lines follow, each with two positive integers $pos,t$, representing the position of a faith cluster and the amount of faith in that cluster. It is not guaranteed that all $pos$ are distinct.

Then $k$ lines follow, each with two integers $u,v$, representing a directed edge from node $u$ to node $v$.

Output Format

A single line containing one integer $x$, representing the maximum value of (amount of faith collected $-$ spirit power cost).

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

2

Hint

Sample Explanation:

The graph is as shown below:

Node $2$ has $2$ faith, node $4$ has $3$ faith, and node $6$ has $4$ faith.

Sanae can teleport a distance of $1$ or $2$ edges, with costs $3$ and $2$ respectively.

One optimal plan is to teleport from node $1$ to node $6$ at a cost of $2$, collect the $4$ faith at node $6$, and then stop. Faith $-$ cost $= 2$.

Constraints:

Translated by ChatGPT 5