题目描述

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.

题目大意

【题目描述】

随着广东的建设与发展，越来越多人选择来到广东开始新生活。在一片新建的小区，有 $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$。

3
4 5
1 100
100 1
100 1
100 1
2 2
1 10
1 10
2 3
100 50
1 1000

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