406030: GYM102220 B Balanced Diet

Taylor is wandering in a milk candy store. The store has $$$m$$$ types of sweets and there are $$$n$$$ sweets in the store. The $$$i$$$-th sweet has the value of $$$a_i$$$, and it is of type $$$b_i$$$.

Taylor is planning to buy some sweets in the store, each sweet can be bought at most once. He will buy at least one sweet. Taylor knows that a balanced diet is important, the value of a sweet set is measured as $$$\frac{S}{C}$$$, where $$$S$$$ denotes the sum of $$$a_i$$$ and $$$C$$$ denotes the maximum number of occurrences among all types of sweets.

Assume Taylor selects $$$p_i$$$ sweets of type $$$i$$$, it is not welcomed if $$$1\leq p_i<l_i$$$. Note that $$$p_i$$$ can also be $$$0$$$ and $$$p_i$$$ can be everything when $$$l_i=1$$$.

Please write a program to help Taylor find the sweet set with maximum value.

The first line of the input contains an integer $$$T(1\leq T\leq 1000)$$$, denoting the number of test cases.

In each test case, there are two integers $$$n,m(1\leq n,m\leq 100000)$$$ in the first line, denoting the number of sweets and types.

In the second line, there are $$$m$$$ integers $$$l_1,l_2,...,l_m(1\leq l_i\leq n)$$$.

For the next $$$n$$$ lines, each line contains two integers $$$a_i,b_i(1\leq a_i\leq 10^8,1\leq b_i\leq m)$$$, denoting each sweet.

It is guaranteed that $$$\sum n\leq 10^6$$$ and $$$\sum m\leq 10^6$$$, and there always exists a valid sweet set.

For each test case, print a single line of format u/v, denoting the maximum value $$$\frac{u}{v}$$$. Note that you should guarantee that $$$\gcd(u,v)=1$$$.

2
2 1
2
7 1
2 1
3 2
1 2
2 1
5 2
3 2

9/2
5/1