Belief Collection in the Village

You are given a directed acyclic graph (DAG) representing a village with m nodes and k directed edges. Every edge has a length of 1. In some nodes there is a cluster of faith with a given positive integer value. There are exactly n clusters located on different nodes; note that node 1 always contains a cluster. When Sanae visits a node that contains a faith cluster, she collects all the faith in that cluster (each cluster can only be collected once).

Sanae starts at node 1. She can travel along any path that follows the directed edges, and may end her journey at any node of her choice. In addition to walking along edges (which is free), Sanae has learned teleportation. There are two types of teleportation moves:

• A small teleport: it moves exactly a units (edges) and costs w_a spiritual power.
• A big teleport: it moves exactly b units (edges) and costs w_b spiritual power.

It is guaranteed that a ≤ b (however, note that it is not necessarily true that w_a < w_b).

Sanae’s journey is valid if every move is along a path in the DAG. That is, if she uses a teleport from node u to node v then there must exist a simple path from u to v whose length is exactly the teleport distance (either a or b). When teleporting, she does not collect the faith in the intermediate nodes (only the destination node’s faith is collected upon arrival).

Your task is to help Sanae plan a route starting from node 1 and ending at any node, so as to maximize the total gain defined as:

[ \text{Total Gain} = \text{(sum of faith collected)} - \text{(total spiritual power spent on teleports)}. ]

Input constraints: You may assume that the graph is small enough (e.g. m up to a few hundreds) that a solution which examines all paths with the given teleport moves will run in time.

inputFormat

The input is given as follows:

m n k a b w_a w_b
u1 f1
... (n lines: each contains a node index u and its faith value f)
(u and v denote a directed edge from node u to node v, each of the next k lines contains two integers):
 u1 v1
 u2 v2
 ...
 uk vk

Note: It is guaranteed that node 1 is among the nodes with a faith cluster.

outputFormat

Output a single integer, the maximum possible value of (total faith collected - total teleport cost) that Sanae can achieve.

sample

5 3 4 1 2 5 3
1 10
3 5
5 20
1 2
2 3
3 4
4 5

35