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 <= 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 <= T <= 1000)$, denoting the number of test cases.
In each test case, there are two integers $n, m (1 <= n, m <= 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 <= l_i <= n)$.
For the next $n$ lines, each line contains two integers $a_i, b_i (1 <= a_i <= 10^8, 1 <= b_i <= m)$, denoting each sweet.
It is guaranteed that $sum n <= 10^6$ and $sum m <= 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$.
## Input
The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there are two integers $n, m (1 <= n, m <= 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 <= l_i <= n)$.For the next $n$ lines, each line contains two integers $a_i, b_i (1 <= a_i <= 10^8, 1 <= b_i <= m)$, denoting each sweet.It is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$, and there always exists a valid sweet set.
## Output
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$.
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of vertices of a convex polygon.
Let $ P_i = (x_i, y_i) \in \mathbb{R}^2 $ for $ i = 0, 1, \dots, n-1 $ be the vertices in counterclockwise order, with $ P_n = P_0 $, $ P_{n+1} = P_1 $.
Let $ Q = (x_Q, y_Q) \in \mathbb{R}^2 $ be a point inside or on the boundary of the polygon.
**Constraints**
1. $ 3 \leq n \leq 50 $
2. All coordinates satisfy $ -10^3 \leq x_i, y_i, x_Q, y_Q \leq 10^3 $
3. $ Q $ lies inside or on the boundary of the convex polygon defined by $ \{P_0, P_1, \dots, P_{n-1}\} $
**Objective**
Simulate rolling the polygon along a straight line, starting with edge $ P_0P_1 $ on the line. At each step $ i = 0, 1, \dots, n-1 $, rotate the polygon counterclockwise about vertex $ P_i $ until the next edge $ P_iP_{i+1} $ lies on the line. The rolling stops when edge $ P_0P_1 $ returns to the line.
For each rotation about $ P_i $, the point $ Q $ traces a circular arc centered at $ P_i $ with radius $ \|Q - P_i\| $, and angle equal to the external angle $ \theta_i = \pi - \alpha_i $, where $ \alpha_i $ is the internal angle at $ P_i $.
The total trajectory length is:
$$
L = \sum_{i=0}^{n-1} \|Q - P_i\| \cdot (\pi - \alpha_i)
$$
where $ \alpha_i $ is the internal angle at vertex $ P_i $, computed from vectors $ \vec{v}_1 = P_{i-1} - P_i $ and $ \vec{v}_2 = P_{i+1} - P_i $ as:
$$
\alpha_i = \angle(\vec{v}_1, \vec{v}_2) = \arccos\left( \frac{\vec{v}_1 \cdot \vec{v}_2}{\|\vec{v}_1\| \|\vec{v}_2\|} \right)
$$
Output $ L $ rounded to 3 decimal places.