{"problem":{"name":"[GDCPC 2023] New Houses","description":{"content":"With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $n$ people moving into $m$ houses","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9693"},"statements":[{"statement_type":"Markdown","content":"With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $n$ people moving into $m$ houses which are arranged in a row. The houses are numbered from $1$ to $m$ (both inclusive). House $u$ and $v$ are neighboring houses, if and only if $|u-v|=1$. We need to assign each person to a house so that no two people will move into the same house. If two people move into a pair of neighboring houses, they will become neighbors of each other.\n\nSome people like to have neighbors while some don't. For the $i$-th person, if he has at least one neighbor, his happiness will be $a_i$; Otherwise if he does not have any neighbor, his happiness will be $b_i$.\n\nAs the planner of this community, you need to maximize the total happiness.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $m$ ($1 \\le n \\le 5 \\times 10^5$, $1 \\le m \\le 10^9$, $n \\le m$) indicating the number of people and the number of houses.\n\nFor the following $n$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \\le a_i, b_i \\le 10^9$) indicating the happiness of the $i$-th person with and without neighbors.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the maximum total happiness.\n\n[samples]\n\n## Note\n\nFor the first sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ to $4$ move into house $3$ to $5$. Thus, person $1$ have no neighbors while person $2$ to $4$ have neighbors. The answer is $100 + 100 + 100 + 100 = 400$. Of course, we can also let person $2$ to $4$ move into house $1$ to $3$ and let person $1$ move into house $5$. This will also give us $400$ total happiness.\n\nFor the second sample test case, as there are only $2$ houses, person $1$ and $2$ have to be neighbors. The answer is $1 + 1 = 2$.\n\nFor the third sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ move into house $3$. Thus, both of them have no neighbors. The answer is $50 + 1000 = 1050$.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9693","tags":["2023","广东","O2优化","省赛/邀请赛"],"sample_group":[["3\n4 5\n1 100\n100 1\n100 1\n100 1\n2 2\n1 10\n1 10\n2 3\n100 50\n1 1000","400\n2\n1050"]],"created_at":"2026-03-03 11:09:25"}}