Maniacal Midsummer Marathon 2014 by AL, TL, JJ

Problem F: Electricity Grid

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 ≤ N ≤ 100) substations and M (0 ≤ M ≤ 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 ≤ E_i ≤ 100000) megajoules. Through field research, your company has determined that substation i supplies the company with a monthly profit of P_i (−10000000 ≤ P_i ≤ 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×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 Format

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 Format

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×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.)

All Submissions
Best Solutions

Point Value: 25 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Jul 15, 2014
Authors: FatalEagle, Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)