Es stehen $n$ Soldaten in einer Reihe. Zu Beginn hat der Soldat mit der Nummer $i$ die Lebenspunkte $a_i$.

Du kannst beliebig viele Angriffe ausführen, auch keinen. Bei jedem Angriff wählst du ein Intervall $[l,r]$ mit $1\le l\le r\le n$ und verringerst die Lebenspunkte aller Soldaten, deren Nummer in diesem Intervall liegt, um $1$. Jeder Angriff kostet $m$.

Wenn nach allen Angriffen die Lebenspunkte des $i$-ten Soldaten höchstens $0$ betragen, erhältst du den Ertrag $b_i$. Da sich unter den Soldaten sowohl Feinde als auch Freunde befinden, kann $b_i$ negativ sein. Beachte, dass der Ertrag jedes Soldaten nur einmal erzielt wird.

Du sollst einen Angriffsplan finden, der die Summe der Erträge abzüglich der Gesamtkosten maximiert. Formal seien $k$ die Anzahl der Angriffe in deinem Plan und $c_i$ die endgültigen Lebenspunkte des $i$-ten Soldaten. Setze $p_i=1$, falls $c_i\le0$, andernfalls $p_i=0$. Du sollst also $(\sum_{i=1}^{n}p_i\times b_i)-m\times k$ maximieren. Auszugeben ist lediglich der größtmögliche Wert der Summe der Erträge abzüglich der Gesamtkosten.

Eingabe

Lies die Daten aus der Datei soldier.in.

Diese Aufgabe enthält mehrere Testfälle.

Die erste Eingabezeile enthält eine positive ganze Zahl $T$, die Anzahl der Testfälle.

Danach folgen die Testfälle der Reihe nach. Jeder Testfall hat folgendes Format:

Die erste Zeile enthält zwei ganze Zahlen $n,m$, die Anzahl der Soldaten und die Kosten eines einzelnen Angriffs.

Die nächsten $n$ Zeilen enthalten jeweils zwei ganze Zahlen $a_i,b_i$, die Lebenspunkte und den Ertrag des jeweiligen Soldaten.

Ausgabe

Schreibe die Ausgabe in die Datei soldier.out.

Gib für jeden Testfall eine Zeile mit einer ganzen Zahl aus: den größtmöglichen Wert der Summe der Erträge abzüglich der Gesamtkosten unter allen möglichen Plänen.

Beispiele

Eingabe 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

Ausgabe 1

12
6
7

Hinweis

Im ersten Testfall besteht ein optimaler Plan aus drei Angriffen auf die Intervalle $[1,5]$, $[2,4]$ und $[4,4]$. Die endgültige Folge der Lebenspunkte ist $(0,0,-1,0,4)$, der Ertrag beträgt $b_1+b_2+b_3+b_4=15$, und die Kosten betragen $3\times1=3$. Es lässt sich beweisen, dass kein besserer Plan existiert; daher wird $15-3=12$ ausgegeben.

Im zweiten Testfall besteht ein optimaler Plan aus zwei Angriffen auf die Intervalle $[1,1]$ und $[3,3]$.

Im dritten Testfall besteht ein optimaler Plan aus einem Angriff auf das Intervall $[1,3]$.

Teilaufgaben

Mit $\sum n$ wird die Summe von $n$ über alle Testfälle einer Testdatei bezeichnet. Für alle Testfälle gilt:

• $1\le T\le5\times10^5$;
• $1\le n,\sum n\le5\times10^5$, $1\le m\le10^9$;
• $\forall 1\le i\le n$, $1\le a_i\le10^9$, $-10^9\le b_i\le10^9$.