有 $n$ 個士兵排成一行。最初，編號係 $i$ 嘅士兵有 $a_i$ 點血量。

你可以進攻若干次，亦可以唔進攻。每次進攻，你可以揀一段區間 $[l,r]$，其中 $1\le l\le r\le n$，令編號喺呢段區間入面嘅士兵血量減少 $1$。每次進攻都要付出 $m$ 嘅代價。

所有進攻結束之後，如果第 $i$ 個士兵嘅血量唔超過 $0$，你就會得到 $b_i$ 嘅收益。由於士兵入面敵友混雜，$b_i$ 有可能係負數。留意每個士兵嘅收益只會獲得一次。

你要搵出一個進攻方案，令總收益減總代價最大。形式化噉講，假設你嘅方案進攻咗 $k$ 次，第 $i$ 個士兵最後嘅血量係 $c_i$；當 $c_i\le0$ 時令 $p_i=1$，否則令 $p_i=0$，你就要最大化 $$ \left(\sum_{i=1}^{n}p_i\times b_i\right)-m\times k. $$ 最後，你只需要畀出總收益減總代價嘅最大值。

輸入格式

由檔案 soldier.in 讀入資料。

呢題有多組測試資料。

輸入第一行有一個正整數 $T$，代表測試資料組數。

跟住依次輸入每組測試資料，每組嘅格式如下：

第一行有兩個整數 $n,m$，分別代表士兵數量同每次進攻嘅代價。

跟住有 $n$ 行，每行有兩個整數 $a_i,b_i$，分別描述每個士兵嘅血量同收益。

輸出格式

將結果輸出到檔案 soldier.out。

對每組資料輸出一行，當中有一個整數，代表所有可能方案入面，總收益減總代價嘅最大值。

樣例

輸入格式 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,5]$、$[2,4]$、$[4,4]$。最後嘅血量序列係 $(0,0,-1,0,4)$，收益係 $b_1+b_2+b_3+b_4=15$，代價係 $3\times1=3$。可以證明冇比呢個方案更好嘅方案，所以輸出 $15-3=12$。

第二組測試資料入面，其中一個最優方案係進攻兩次，分別揀區間 $[1,1]$、$[3,3]$。

第三組測試資料入面，其中一個最優方案係進攻一次，揀區間 $[1,3]$。

子任務

用 $\sum n$ 表示單個測試點入面所有測試資料嘅 $n$ 加埋嘅總和。所有測試資料都保證：

• $1\le T\le5\times10^5$。
• $1\le n,\sum n\le5\times10^5$，$1\le m\le10^9$。
• 對所有 $1\le i\le n$，$1\le a_i\le10^9$，$-10^9\le b_i\le10^9$。