有 $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$，令 $p_i$ 在 $c_i\le0$ 時為 $1$，否則為 $0$，則你需要最大化 $(\sum_{i=1}^n p_i\times b_i)-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$；
• $\forall1\le i\le n,1\le a_i\le10^9,-10^9\le b_i\le10^9$。