$n$ 人の兵士が一列に並んでいます。初め、番号 $i$ の兵士の体力は $a_i$ です。

あなたは何回か攻撃を行えます（1 回も行わなくてもかまいません）。1 回の攻撃では区間 $[l,r]$（$1\le l\le r\le n$）を選び、この区間に番号が含まれる兵士全員の体力を $1$ 減らせます。攻撃 1 回につきコスト $m$ がかかります。

すべての攻撃が終わった後、兵士 $i$ の体力が $0$ 以下なら、利益 $b_i$ を得ます。兵士には敵と味方が混在しているため、$b_i$ は負の場合もあります。各兵士から利益を得られるのは 1 回だけです。

利益の総和からコストの総和を引いた値を最大にする攻撃計画を求めてください。形式的には、攻撃を $k$ 回行い、兵士 $i$ の最終的な体力を $c_i$ とします。$c_i\le 0$ のとき $p_i=1$、そうでないとき $p_i=0$ とすると、最大化すべき値は $\left(\sum_{i=1}^{n}p_i\times b_i\right)-m\times k$ です。最終的には、利益の総和からコストの総和を引いた値の最大値だけを求めればよいです。

入力

ファイル soldier.in からデータを読み込みます。

複数のテストケースがあります。

入力の 1 行目には、テストケース数を表す正の整数 $T$ が与えられます。

続いて各テストケースが順に与えられます。各テストケースの形式は以下のとおりです。

1 行目には整数 $n,m$ が与えられ、それぞれ兵士の人数と攻撃 1 回のコストを表します。

続く $n$ 行にはそれぞれ 2 つの整数 $a_i,b_i$ が与えられ、各兵士の体力と利益を表します。

出力

ファイル soldier.out に出力してください。

各テストケースについて、可能なすべての計画における「利益の総和からコストの総和を引いた値」の最大値を、整数 1 つからなる 1 行に出力してください。

入出力例

入力 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

注記

1 番目のテストケースでは、区間 $[1,5],[2,4],[4,4]$ をそれぞれ選んで 3 回攻撃する計画が最適解の 1 つです。最終的な体力の列は $(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]$ をそれぞれ選んで 2 回攻撃する計画が最適解の 1 つです。

3 番目のテストケースでは、区間 $[1,3]$ を選んで 1 回攻撃する計画が最適解の 1 つです。

小課題

$\sum n$ を、1 つのテストファイルに含まれる全テストケースの $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 i\le n$ について、$1\le a_i\le 10^9$、$-10^9\le b_i\le 10^9$。