题目描述

大家都知道CPP跑去旅游了。

这一天。CPP来到了一个新的景区。景区有 $N$ 个景点，每个景点有一个票价 $c_i$ 和CP对这个景点的向往度 $v_i$。为了吸引CPP大神（主要是神牛牛牛经过的地方可以光明正大的涨票价），旅游开发公司给出了 $m$ 条优惠。每一条优惠的内容可以表示为一对的 ($a$ $b$)，意思是如果CPP现在在编号为 $a$ 的景点，那么他可以免费前往编号为 $b$ 的景点（此时若有一条优惠内容是 ($b$ $c$) 则CPP还可以继续前往编号为 $c$ 的景点）。因为CPP还有很多的计划，所以他只会购买一次门票。为了确保能引起CPP的兴趣，旅游开发公司的工作人员需要知道在现有的优惠方案下，CPP的最高满意度是多少。其中最高满意度定义为（CPP游览的所有景区的兴趣值之和/CPP进入景区的景点票价）。可以重复经过某个景点，但是CPP对该景点的兴趣值只计算一次。

题目中给定的所有数据均为正整数。

输入格式

第$1$行两个整数 $n$ $m$

第$2～n+1$行每行两个整数 $c_i$ $v_i$

第$n+2$行～第$n+m+1$行每行两个整数 $a$ $b$

输出格式

一个数 $ans$ 表示CPP的最大满意度，保留两位小数.

样例输入

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

样例输出

4.67

数据规模与约定

$For$ $40 Pts$ $n<=1000, m<=10000$

$For$ $100 Pts$ $n<=20000, m<=100000$