几位编程竞赛选手最终创办了初创公司。其中两人创建了 Eeet，这是一个社交餐厅评分系统。Eeet 的每位成员都可以给餐厅打一个 0 到 10 之间的整数分，或者不打分。一个人看到的评分是其所有给出评分的朋友的平均分。特别地，给出 0 分通常会降低其朋友看到的评分，而选择不打分则不会产生影响。如果一个用户的任何朋友都没有给某家餐厅打分，那么该餐厅就不会出现在该用户的界面中。

Picture by Desiree Williams, cc by-nd

另外两名往届选手开了一家名为“臭鱼”（The Smelly Fish）的餐厅，但他们很困惑为什么没有人来用餐。通过实验，他们发现每个人都愿意来餐厅一次（出于某种无法解释的原因，没有顾客会再次光顾），并消费 $100y$ 瑞典克朗，其中 $y$ 是他们在 Eeet 上看到的评分。每个人都使用银行卡支付，且金额不进行四舍五入。

然而，他们目前还没有收到任何评分，而且他们购买的所有新鲜农产品都有变质的风险。因此，他们选择贿赂一些人，让他们在 Eeet 上留下评分。对于每个人，我们已知他们会根据函数 $\sqrt{x/a}$ 给“臭鱼”餐厅打分，其中 $a$ 是取决于个人的常数，$x$ 是贿赂金额（单位：瑞典克朗）。注意，被贿赂 0 瑞典克朗的人会留下 0 分（而不是不打分），最高评分为 10 分，且接受贿赂的人知道这个计划，因此不会去餐厅用餐。

你的任务是最大化餐厅的利润，即顾客的消费减去贿赂所花费的金额。

输入格式

第一行包含三个整数 $n, m$ 和 $k$ ($1 \le m \le 10^5, 0 \le n \le 10^5, 0 \le k \le n$)，分别表示 Eeet 的人数、友谊关系的数量以及我们要贿赂的人数。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \le a, b \le n$)，表示一对朋友的 ID。没有无序对 $\{a, b\}$ 会出现超过一次。

接下来的 $k$ 行，每行包含两个整数 $i$ ($1 \le i \le n$)，表示我们要贿赂的人的 ID，以及参数 $a_i$ ($1 \le a_i \le 1000$)。没有 ID 会出现超过一次。

输出格式

输出一行，表示餐厅能获得的最大利润。答案的绝对误差或相对误差在 $10^{-6}$ 以内均可被接受。

样例

输入格式 1

10 1 1
1 2
1 3

输出格式 1

276