Maniacal Midsummer Marathon 2014 by AL, TL, JJ

You have just been hired as the new manager of a city's main power plant. Going to work on your first day, you learned that the company has been losing massive amounts of money. After some investigating, you've discovered that this is because the company has been delivering unnecessarily high amounts of energy to the substations in the city's electricity grid!

The electricity grid consists of $N$ $(1\le N\le 100)$ substations and $M$ $(0\le M\le 400)$ wires connecting the substations. These substations are interspersed throughout the city and are responsible for distributing power to consumers. Electricity can only travel in one direction along each wire, and the direction on a wire can never be reversed. The substations are each labeled with a unique integer from $1$ to $N$. Substation $i$ has a monthly energy usage of $E_i$ $(1\le E_i\le 100000)$ megajoules. Through field research, your company has determined that substation $i$ supplies the company with a monthly profit of $P_i$ $(-10000000\le P_i\le 10000000)$ dollars.

Some of these substations are just too wasteful, so it's time for a reform! You would like to pick out some subset of all of the substations in the entire city to keep for the long term. There is a catch: for any of the substations you wish to keep, you must keep all the substations that depend on it for electricity, directly or indirectly. More specifically, in order to keep a substation $i$, any substation $j$ such that electricity can flow from $i$ to $j$ using any series of connected wires/substations, must also be kept.

Just when you thought your new job couldn't get any harder, the tyrants from the EPA came over and complained that the maximum energy usage across your substations is too high, and will harm the environment. Every month, they will fine you $A$ dollars for every megajoule of $E_{max}$, your maximum energy usage. The value of $E_{max}$ for a set of substations is the maximum $E_i$ across all $i$ in the set. Therefore, your total monthly profit after the reform is the sum of all $P_i$ values for the stations you choose to keep, subtract $A\times E_{max}$ across those stations. The fine per megajoule will be a nonnegative integer less than $10000$.

To save yourself from some headaches, you might as well write a program to determine the highest possible total monthly profit that you can obtain by keeping a subset of the power substations.

Input Specification

Line $1$: three integers $N$, $M$, and $A$, representing the number of substations, the number of wires, and the EPA fine factor.
Next $N$ lines: two integers $P_i$ and $E_i$, representing the profit and monthly energy usage of station $i$.
Next $M$ lines: two integers $a_i$ and $b_i$, indicating that there is a one-way wire from substation $a_i$ to $b_i$.

Output Specification

A single integer representing the highest possible total monthly profit (in dollars) obtainable by selecting a subset of all of the $N$ substations.

Sample Input 1

4 3 1
5 3
-7 2
15 4
-3 1
1 2
2 3
3 4

Sample Output 1

8

Explanation for Sample 1

There are $4$ substations with profits $\{\$5,-\$7,\$15,-\$3\}$ and monthly energy usages of $\{3,2,4,1\}$.
If we choose to keep substations $3$ and $4$, then the monthly subtotal profit is $\$(15+(-3))=\$12$.
The EPA fine will be $\$1\times max(4,1)=\$4$, so the total monthly profit is $\$12-\$4=\$8$. In fact, $\$8$ is the best answer for this example.

Sample Input 2

4 4 1
-1 1
2 1
-3 1
4 1
1 2
2 3
3 4
4 1

Sample Output 2

1

Explanation for Sample 2

It's possible that cyclic dependencies exist, as shown by these four substations. You must take either all or none, and your best choice is to take them all for a profit of $\$1$.

Sample Input 3

3 3 8
15 2
-10 1
10 1
1 2
3 2
1 3

Sample Output 3

0

Explanation for Sample 3

It is not profitable to keep any substation because the fine by the EPA would always be more than the profit obtainable from keeping any valid subset of substations.
(With no functional substations anywhere, you should probably be heading to the bank to file bankruptcy for your company.)