标记数轴

时间限制：1s

空间限制：256 MB

题目描述

在一个长度为 $m - 1$ 的数轴上，共有 $m$ 个整数点（$1 \rightarrow m$），如果两个整数点 $a$ 和 $b$ 满足 $|a - b| = 1$ ，则说明两个整数点 相邻。

$zms$ 现在想要无序地在这个数轴上标出 $n$ 个整数点，并为第 $i$ 个标记的整数点按如下方式记录价值：

• 如果该标记点有相邻的标记点（即有至少一个相邻的标记的整数点），则该点价值为 $s_i$ 。
• 如果该标记点没有相邻的标记点，则该点价值为 $l_i$ 。

$zms$ 希望你能帮他选择标记的整数点以使得所有标记的整数点的价值总和最大。

注意： 第 $i$ 个标记的整数点可以在任意没有标记过的位置。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $m$（$1 \le n \le 5 \times 10^5$，$1 \le m \le 10^9$，$n \le m$），表示需要标记的点数和数轴上的总点数。

对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $s_i$ 和 $l_i$（$1 \le s_i, l_i \le 10^9$），表示第 $i$ 个标记点在有相邻点和没有相邻点时的价值。

保证所有数据 $n$ 之和不超过 $10^6$。

输出格式

每组数据输出一行一个整数表示最大价值总和。

样例输入

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

样例解释

对于第一组样例数据，最优方案是第 $1$ 个标记用来标记整数点 $1$ ，第 $2 \rightarrow 4$ 个标记用来标记整数点 $3 \rightarrow 5$ 。这样，第 $1$ 个标记点没有相邻标记点，而第 $2$ 到 $4$ 个标记点都有相邻标记点。答案为 $100 + 100 + 100 + 100 = 400$。当然，也可以让第 $2 \rightarrow 4$ 个标记用来标记整数点 $1 \rightarrow 3$，第 $1$ 个标记用来标记整数点 $5$，也能得到 $400$ 的总满意度。

对于第二组样例数据，由于数轴只有 $2$ 个整数点，因此第 $1$ 和第 $2$ 个标记必须相邻。答案为 $1 + 1 = 2$。

对于第三组样例数据，最优方案是让第 $1$ 个标记用来标记整数点 $1$，第 $2$ 个标记用来标记整数点 $3$。这样，两个标记即没有相邻。答案为 $50 + 1000 = 1050$。

数据范围与约定

对于 50% 的测试数据，满足 $T\le100$，$1 \le n \le 500$，$1 \le m \le 10^4$，$n \le m$，$1 \le s_i, l_i \le 10^3$ ；

对于全部的测试数据，满足 $1 \le n \le 5 \times 10^5$，$1 \le m \le 10^9$，$n \le m$，$1 \le s_i, l_i \le 10^9$

保证所有数据 $n$ 之和不超过 $10^6$。