{"problem":{"name":"G. Happiness","description":{"content":"_Pang_ has graduated from college $3$ years and he really misses the time he spent with ICPC(Interspecies Collegiate Pokemon Camp).  There are $10$ problems in one contest in ICPC. $n$ participating ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10247G"},"statements":[{"statement_type":"Markdown","content":"_Pang_ has graduated from college $3$ years and he really misses the time he spent with ICPC(Interspecies Collegiate Pokemon Camp).\n\n There are $10$ problems in one contest in ICPC. $n$ participating teams have $300$ minutes to solve them. After the contest, teams are ranked according to the most problems solved. Teams who solve the same number of problems are ranked by least total time. The total time is the sum of the time consumed for each problem solved. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submittal of the first accepted run plus 20 penalty minutes for every previously rejected run for that problem. There is no time consumed for a problem that is not solved. If two teams tie, their _solution time list_s are calculated. A team's solution time list is a list consisting of solution times of all problems solved by that team, sorted in descending order. The solution time of one problem is the time elapsed from the beginning of the contest to the submittal of the first accepted run of that problem. (We do not add a penalty for the solution time.) The team with a lexicographically smaller solution time list has a better rank. A list $(a_1, \\\\dots, a_k)$ is lexicographically smaller than $(b_1, \\\\dots, b_k)$ if there exists an integer $i in [ 1, k ]$ such that $a_i < b_i$ and $a_j = b_j$ for all integers $j in [ 1, i)$. If teams still tie, _Pang_'s team is assumed to have a better rank. \n\nAfter determining the rank, prizes will be awarded. Initially, a team with rank $r$ will get $floor.l 5000 \\/ r floor.r$ happiness. Then medals are awarded: Teams with rank $1$ to $floor.l n \\/ 10 floor.r$ are awarded gold medal. The _happiness_ of receiving a gold medal is $1200$. Teams with rank $floor.l n \\/ 10 floor.r + 1$ to $3 floor.l n \\/ 10 floor.r$ are awarded silver medal. The _happiness_ of receiving a silver medal is $800$. Teams with rank $3 floor.l n \\/ 10 floor.r + 1$ to $6 floor.l n \\/ 10 floor.r$ are awarded bronze medal. The _happiness_ of receiving a bronze medal is $400$. In addition to medals, for each problem, the team solved it first gets $800$ happiness. The team with at least one solution and the smallest solution time overall teams and all problems gets an extra $700$ happiness. The team with at least one solution and the largest solution time overall teams and all problems gets an extra $500$ happiness. In the case of a tie, _Pang_'s team can always get happiness.\n\nThere were $n$ teams in a contest _Pang_ participated. He remembers all the submissions (time and verdict) of all other teams. For each problem, he also remembers if he knew the solution to that problem and the number of rejected runs and times he needed to solve it.\n\nIf _Pang_ solved problems in the wisest order, what is the maximum happiness he could get? Note that _Pang_ cannot solve any problem after $300$ minutes from the beginning of the contest (He can solve problems at exactly 300 minutes). Once _Pang_ solves a problem, he needs to submit it immediately and solve another one. He can't postpone his submission to get the last submission happiness.\n\nThe first line contains an integer $n$ denoting the number of teams ($10 <= n <= 300$, $n$ is a multiple of $10$).\n\nEach of the next $n -1$ lines describes one team and contains the statuses of the $10$ problems. For each problem, if it is not solved by the team, the status contains a single character \"-\". Otherwise, the status contains two integers $t$ and $w$ separated by a single space denoting the solution time and the number of rejected runs before the solution time ($1 <= t <= 300, 0 <= w <= 10$). Statuses of different problems are separated by \",\".\n\nThe last line describes _Pang_'s team. For each problem, if _Pang_ did not know how to solve it, the status contains a single character \"-\". Otherwise, the status contains two integers $x$ and $y$ separated by a single space denoting the required time and the number of rejected runs before _Pang_ could solve it ($1 <= x <= 300, 0 <= y <= 10$). Statuses of different problems are separated by \",\".\n\nThere are no extra spaces and other characters in the statuses of _Pang_ and other teams.\n\nOutput one integer — the maximum happiness.\n\nNote that the sample input and sample output contain wrapped lines to fit in the width of page.\n\n## Input\n\nThe first line contains an integer $n$ denoting the number of teams ($10 <= n <= 300$, $n$ is a multiple of $10$).Each of the next $n -1$ lines describes one team and contains the statuses of the $10$ problems. For each problem, if it is not solved by the team, the status contains a single character \"-\". Otherwise, the status contains two integers $t$ and $w$ separated by a single space denoting the solution time and the number of rejected runs before the solution time ($1 <= t <= 300, 0 <= w <= 10$). Statuses of different problems are separated by \",\".The last line describes _Pang_'s team. For each problem, if _Pang_ did not know how to solve it, the status contains a single character \"-\". Otherwise, the status contains two integers $x$ and $y$ separated by a single space denoting the required time and the number of rejected runs before _Pang_ could solve it ($1 <= x <= 300, 0 <= y <= 10$). Statuses of different problems are separated by \",\".There are no extra spaces and other characters in the statuses of _Pang_ and other teams.\n\n## Output\n\nOutput one integer — the maximum happiness.\n\n[samples]\n\n## Note\n\nNote that the sample input and sample output contain wrapped lines to fit in the width of page.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 10 \\leq n \\leq 300 $, $ n \\equiv 0 \\pmod{10} $, be the number of teams.  \nLet $ P = \\{1, 2, \\dots, 10\\} $ be the set of problems.  \nFor each team $ t \\in \\{1, \\dots, n\\} $, define:  \n- $ S_t \\subseteq P $: set of problems solved by team $ t $.  \n- For each $ p \\in S_t $:  \n  - $ \\tau_{t,p} \\in \\mathbb{Z}^+ $: solution time (submission time of first accepted run).  \n  - $ w_{t,p} \\in \\mathbb{Z}_{\\geq 0} $: number of rejected runs before acceptance.  \n- For unsolved problems $ p \\notin S_t $: $ \\tau_{t,p} = \\infty $, $ w_{t,p} = 0 $.  \n\nLet team $ n $ be Pang’s team.  \nFor Pang’s team, for each $ p \\in P $, if $ p $ is solvable, he can choose to solve it at time $ x_p $ with $ y_p $ rejected runs (given); otherwise, $ p \\notin S_n $ (cannot solve).  \nPang can choose any subset $ S_n \\subseteq P $ of solvable problems and any order $ \\pi $ of solving them, such that cumulative time $ \\sum_{i=1}^{|S_n|} (x_{\\pi(i)} + 20 \\cdot y_{\\pi(i)}) \\leq 300 $.  \nOnce solved, submission is immediate.  \n\n**Constraints**  \n1. For all teams $ t \\in \\{1, \\dots, n-1\\} $, $ \\tau_{t,p}, w_{t,p} $ are given.  \n2. For Pang’s team: for each $ p \\in P $, if solvable, $ x_p \\in [1, 300] $, $ y_p \\in [0, 10] $; else, $ p $ is unsolvable.  \n3. Pang’s total time for solved problems: $ \\sum_{p \\in S_n} (x_p + 20 \\cdot y_p) \\leq 300 $.  \n4. Solution times $ \\tau_{n,p} = \\text{cumulative time at submission of } p $ under chosen order $ \\pi $.  \n\n**Ranking Rules**  \nTeams are ranked by:  \n1. **Primary**: Number of solved problems $ |S_t| $, descending.  \n2. **Secondary**: Total penalty time $ \\sum_{p \\in S_t} (\\tau_{t,p} + 20 \\cdot w_{t,p}) $, ascending.  \n3. **Tertiary**: Lexicographically descending solution time list $ (\\tau_{t,p})_{p \\in S_t} $ sorted in descending order; lexicographically smaller list ranks higher.  \n4. **Final tiebreaker**: Pang’s team always ranks better than any tied team.  \n\n**Happiness Calculation**  \nPang’s total happiness is sum of:  \n\n1. **Rank-based prize**: $ \\left\\lfloor \\frac{5000}{r} \\right\\rfloor $, where $ r $ is Pang’s final rank.  \n2. **Medal bonuses**:  \n   - Gold ($ r \\leq \\left\\lfloor \\frac{n}{10} \\right\\rfloor $): $ +1200 $  \n   - Silver ($ \\left\\lfloor \\frac{n}{10} \\right\\rfloor < r \\leq 3\\left\\lfloor \\frac{n}{10} \\right\\rfloor $): $ +800 $  \n   - Bronze ($ 3\\left\\lfloor \\frac{n}{10} \\right\\rfloor < r \\leq 6\\left\\lfloor \\frac{n}{10} \\right\\rfloor $): $ +400 $  \n3. **First-solve bonuses**: $ +800 $ for each problem $ p \\in S_n $ such that $ \\tau_{n,p} < \\tau_{t,p} $ for all $ t \\neq n $ with $ p \\in S_t $.  \n4. **Extreme solution time bonuses**:  \n   - $ +700 $ if $ \\min_{t \\in [1,n], p \\in S_t} \\tau_{t,p} = \\tau_{n,p} $ for some $ p \\in S_n $  \n   - $ +500 $ if $ \\max_{t \\in [1,n], p \\in S_t} \\tau_{t,p} = \\tau_{n,p} $ for some $ p \\in S_n $  \n   (In case of tie, Pang’s team wins.)  \n\n**Objective**  \nMaximize Pang’s total happiness over all feasible subsets $ S_n \\subseteq P $ and all feasible solving orders $ \\pi $ satisfying the time constraint.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10247G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}