P9693 [GDCPC 2023] New Houses

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. Some 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$. As the planner of this community, you need to maximize the total happiness.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The 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. For 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. It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

For each test case output one line containing one integer indicating the maximum total happiness.

For 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. For 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$. For 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$.