P9693 [GDCPC 2023] New Houses

随着广东的建设与发展，越来越多人选择来到广东开始新生活。在一片新建的小区，有 $n$ 个人要搬进 $m$ 栋排成一行的房子，房子的编号从 $1$ 到 $m$（含两端）。房子 $u$ 和 $v$ 相邻，当且仅当 $|u-v|=1$。我们需要为每一个人安排一栋房子，要求所有人入住的房子互不相同。若两个人住进了一对相邻的房子，则这两个人互为邻居。 有的人喜欢自己有邻居，而有的人不喜欢。对于第 $i$ 个人，如果他有至少一位邻居，则他的满意度为 $a_i$；否则如果他没有邻居，则他的满意度为 $b_i$。 您作为小区的规划者，需要最大化所有人的总满意度。

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据： 第一行输入两个整数 $n$ 和 $m$（$1 \le n \le 5 \times 10^5$，$1 \le m \le 10^9$，$n \le m$），表示人数和房子数。 对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$），表示第 $i$ 个人在有邻居和没有邻居时的满意度。 保证所有数据 $n$ 之和不超过 $10^6$。

每组数据输出一行一个整数表示最大总满意度。 **【样例解释】** 对于第一组样例数据，最优方案是让第 $1$ 个人入住房子 $1$，第 $2$ 到 $4$ 个人入住房子 $3$ 到 $5$。这样，第 $1$ 个人没有邻居，而第 $2$ 到 $4$ 个人都有邻居。答案为 $100 + 100 + 100 + 100 = 400$。当然，也可以让第 $2$ 到 $4$ 个人入住房子 $1$ 到 $3$，第 $1$ 个人入住房子 $5$，也能得到 $400$ 的总满意度。 对于第二组样例数据，由于只有 $2$ 栋房子，因此第 $1$ 和第 $2$ 个人必须成为邻居。答案为 $1 + 1 = 2$。 对于第三组样例数据，最优方案是让第 $1$ 个人入住房子 $1$，第 $2$ 个人入住房子 $3$。这样，两个人都没有邻居。答案为 $50 + 1000 = 1050$。

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