{"problem":{"name":"[ICPC 2022 Jinan R]  Skills","description":{"content":" Prof. Pang has $3$ different skills to practice, including soda drinking, fox hunting, and stock investing. We call them Skill $1$, Skill $2$, and Skill $3$. In each of the following $n$ days, Prof. ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9676"},"statements":[{"statement_type":"Markdown","content":"Prof. Pang has $3$ different skills to practice, including soda drinking, fox hunting, and stock investing. We call them Skill $1$, Skill $2$, and Skill $3$. In each of the following $n$ days, Prof. Pang can choose one of the three skills to practice. In the $i$-th day ($1\\le i\\le n$), if Prof. Pang chooses Skill $j$ ($1\\le j\\le 3$) to practice, his level of Skill $j$ will increase by $a_{i,j}$. Initially, Prof. Pang's levels of all skills are $0$.\n\nProf. Pang forgets skills if he does not practice. At the end of each day, if he has not practiced Skill $j$ for $k$ days, his level of Skill $j$ will decrease by $k$. For example, if he practices Skill $1$ on day $1$ and Skill $2$ on day $2$, at the end of day $2$, he has not practiced Skill $1$ for $1$ day and has not practiced Skill $3$ for $2$ days. Then his levels of Skill $1$ and Skill $3$ will decrease by $1$ and $2$, respectively. His level of Skill $2$ does not decrease at the end of day $2$ because he practices Skill $2$ on that day. In this example, we also know that his levels of Skill $2$ and Skill $3$ both decrease by $1$ at the end of day $1$.\n\nProf. Pang's level of any skill will not decrease below $0$. For example, if his level of some skill is $3$ and at the end of some day, this level is decreased by $4$, it will become $0$ instead of $-1$.\n\nProf. Pang values all skills equally. Thus, he wants to maximize the sum of his three skill levels after the end of day $n$. \n\nGiven $a_{i,j}$ ($1\\le i\\le n, 1\\le j\\le 3$), find the maximum sum.\n\n## Input\n\nThe first line contains a single integer $T~(1 \\le T \\le 1000)$ denoting the number of test cases.\n\nFor each test case, the first line contains an integer $n~(1 \\le n \\le 1000)$. The $(i+1)$-th line contains three integers $a_{i,1}, a_{i,2}, a_{i,3}$ ($0\\le a_{i,j}\\le 10000$ for any $1\\le i\\le n, 1\\le j\\le 3$).\n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $1000$.\n\n## Output\n\nFor each test case, output the maximum possible sum of skill levels in one line. \n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9676","tags":["动态规划 DP","2022","O2优化","ICPC","济南"],"sample_group":[["2\n3\n1 1 10\n1 10 1\n10 1 1\n5\n1 2 3\n6 5 4\n7 8 9\n12 11 10\n13 14 15\n","26\n41"]],"created_at":"2026-03-03 11:09:25"}}