{"raw_statement":[{"iden":"statement","content":"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$.\n\nTaylor 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.\n\nAssume 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$.\n\nPlease write a program to help Taylor find the sweet set with maximum value.\n\nThe first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.\n\nIn each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of sweets and types.\n\nIn the second line, there are $m$ integers $l_1, l_2,..., l_m (1 <= l_i <= n)$.\n\nFor 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.\n\nIt is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$, and there always exists a valid sweet set.\n\nFor 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$.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of vertices of a convex polygon.  \nLet $ 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 $.  \nLet $ Q = (x_Q, y_Q) \\in \\mathbb{R}^2 $ be a point inside or on the boundary of the polygon.  \n\n**Constraints**  \n1. $ 3 \\leq n \\leq 50 $  \n2. All coordinates satisfy $ -10^3 \\leq x_i, y_i, x_Q, y_Q \\leq 10^3 $  \n3. $ Q $ lies inside or on the boundary of the convex polygon defined by $ \\{P_0, P_1, \\dots, P_{n-1}\\} $  \n\n**Objective**  \nSimulate 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.  \n\nFor 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 $.  \n\nThe total trajectory length is:  \n$$\nL = \\sum_{i=0}^{n-1} \\|Q - P_i\\| \\cdot (\\pi - \\alpha_i)\n$$  \nwhere $ \\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:  \n$$\n\\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)\n$$  \n\nOutput $ L $ rounded to 3 decimal places.","simple_statement":"Bahiyyah has a convex polygon with n vertices in counter-clockwise order. She rolls it along a straight line, rotating around each vertex one by one, until it returns to the starting position. A point Q inside or on the polygon moves along a path. Calculate the total length of Q’s path during one full roll, rounded to 3 decimal places.","has_page_source":false}