{"problem":{"name":"B. Balanced Diet","description":{"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$. Taylor is plannin","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10222B"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10222B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}