Picture
by Desiree Williams, cc bynd
Several participants in programming competitions end up
founding startup companies. Two of them created Eeet, a social
restaurant rating system. Each member of Eeet can rate a
restaurant with an integer score from $0$ to $10$ or not give a score at all. The
score that a person sees is the average of ratings from the
friends who gave one. In particular, a person giving a score of
$0$ will in general
decrease the rating that their friends see, whereas not giving
a score at all will not affect it. If none of the friends of a
user has given a rating to a restaurant, then the restaurant
does not show up to that user.
Two other past contestants have opened a restaurant, The
Smelly Fish, but they are bewildered as to why nobody is dining
at their establishment. Through experimentation they found out
that each person is willing to come once to the restaurant (for
some inexplicable reason no customer ever returns) and spend
$100y$ SEK, where
$y$ is the rating they see
on Eeet. Everybody pays by card, and money transactions are not
rounded.
However, they did not get any ratings yet, and all the fresh
produce they bought risks going past its prime. Hence they
selected some people to bribe so that they will leave them a
rating in Eeet. For each person, we know that they will give
The Smelly Fish a rating according to the function $\lfloor \sqrt {x}/a\rfloor $, where
$a$ is a constant
depending on the person, and $x$ is the amount of the bribe in SEK.
Note that a person bribed with $0$ SEK will leave a rating of
$0$ (instead of not giving
a rating at all), that the maximum rating is $10$, and that a person that received
a bribe knows about the scheme and will not go to the
restaurant.
Your task is to maximize the profit the restaurant makes,
i.e., the income from customers minus the money spent on
bribes.
Input
The first line contains three integers $n$, $m$, and $k$, ($1
\leq m \leq 10^5$, $0 \leq
n \leq 10^5$, $0 \leq k
\leq n$), the number of people in Eeet, the number of
friendship relations, and the number of people we are going to
bribe.
Each of the next $m$
lines contains two integers, $a$ and $b$ ($1
\leq a,b \leq n$), the ids of a pair of friends. No
unordered pair $\{ a,b\} $
appears more than once.
Each of the next $k$
lines contains two integers $i$ ($1
\leq i \leq n$), the id of a person we are going to
bribe, and the parameter $a_
i$ ($1 \leq a_ i \leq 1\,
000$). No id appears more than once.
Output
Output one line with the maximum profit the restaurant can
make. Answers with an absolute or relative precision up to
$10^{6}$ will be
accepted.
Sample Input 1 
Sample Output 1 
10 1 1
1 2
1 3

276
