育华演习

题目背景

育华社团开展模拟演习训练任务。

题目描述

有 $n$ 名社团成员排成一整排。初始时第 $i$ 名成员的耐久值为 $a_i$。

你可以进行若干轮演习攻击，也可以一轮都不执行。 每一轮攻击可以选定一段连续区间 $([l,r])$，将区间内每名成员的耐久值减去 $1$；每进行一轮攻击需要消耗 $m$ 点社团经费。

全部攻击结束之后： 如果第 $i$ 名成员耐久值 $\le 0$，你可以获得 $b_i$ 的演习积分。注意积分只会获取一次；受演习设定影响，$b_i$ 有可能是负数。

设一共执行了 $k$ 轮攻击，攻击结束后第 $i$ 名成员剩余耐久为 $c_i$。令 $p_i=1$ 当且仅当 $c_i \le 0$，否则 $p_i=0$。 你需要最大化：

$$\left(\sum_{i=1}^n p_i \times b_i\right) - m\times k$$

只输出这个总收益的最大值即可。

输入格式

本题有多组测试数据。 第一行一个正整数 $T$，代表数据组数。

每组数据： 第一行两个整数 $(n,m)$，成员数量，单次攻击消耗的经费。 之后 $n$ 行，每行两个整数 $a_i,b_i$，代表第 $i$ 位成员的初始耐久值、击败后获得的演习积分。

T
n m
a_1 b_1
a_2 b_2
……
a_n b_n
……（多组数据）

输出格式

对每组测试用例输出一行一个整数，表示总收益的最大值。

样例输入 #1

3
5 1
1 3
2 5
1 4
3 3
5 1
3 2
1 5
1 -100
1 5
3 2
1 5
1 -1
1 5

样例输出 #1

12
6
7

样例解释

第一组数据最优方案：执行3轮攻击，分别选取区间 $([1,5],[2,4],[4,4])$。 攻击结束后耐久序列 $(0,0,-1,0,4)$。 获得积分：$b_1+b_2+b_3+b_4=15$，总经费消耗 $3\times 1=3$，总收益 $15-3=12$。

第二组数据最优方案：执行2轮攻击，选取 $([1,1])$、$([3,3])$。

第三组数据最优方案：执行1轮攻击，选取 $([1,3])$。

数据范围

$\sum n$ 表示一个测试点内全部测试数据的 $n$ 之和。

• $1\le T \le 5\times 10^5$
• $1\le n,\sum n \le 5\times 10^5$
• $1\le m \le 10^9$
• $1\le a_i \le 10^9$
• $-10^9 \le b_i \le 10^9$

共20个测试点，每个测试点分值相等，总分100分，单测试点5分。

测试点编号	分值	$\sum n \le$	特殊性质
$1$	$5$	$5\times10^5$	A
$2\sim4$	$15$	$5,000$	B
$5\sim8$	$20$		无
$9\sim12$		$10^5$
$13\sim17$	$25$	$2\times 10^5$
$18\sim20$	$15$	$5\times 10^5$

特殊性质A：所有 $b_i\ge 0$。 特殊性质B：所有 $a_i \le (5,000)$。