W szeregu stoi $n$ żołnierzy. Początkowo żołnierz o numerze $i$ ma $a_i$ punktów życia.

Możesz przeprowadzić dowolną liczbę ataków, także zero. Podczas każdego ataku wybierasz przedział $[l,r]$ ($1\le l\le r\le n$) i zmniejszasz o $1$ liczbę punktów życia wszystkich żołnierzy o numerach z tego przedziału. Każdy atak kosztuje $m$.

Po zakończeniu wszystkich ataków otrzymujesz korzyść $b_i$, jeśli żołnierz $i$ ma nie więcej niż $0$ punktów życia. Ponieważ wśród żołnierzy są zarówno wrogowie, jak i sojusznicy, $b_i$ może być ujemne. Pamiętaj, że korzyść za każdego żołnierza otrzymujesz tylko raz.

Znajdź plan ataków maksymalizujący sumę korzyści pomniejszoną o sumę kosztów. Formalnie, niech plan obejmuje $k$ ataków, a końcowa liczba punktów życia żołnierza $i$ wynosi $c_i$. Przyjmijmy $p_i=1$, gdy $c_i\le 0$, oraz $p_i=0$ w przeciwnym razie. Należy zmaksymalizować $\left(\sum_{i=1}^{n}p_i\times b_i\right)-m\times k$. Wystarczy podać największą możliwą wartość sumy korzyści pomniejszonej o sumę kosztów.

Wejście

Dane należy odczytać z pliku soldier.in.

Zadanie zawiera wiele zestawów danych testowych.

Pierwszy wiersz wejścia zawiera dodatnią liczbę całkowitą $T$, oznaczającą liczbę zestawów danych.

Następnie podane są kolejne zestawy danych. Każdy z nich ma następującą postać:

Pierwszy wiersz zawiera dwie liczby całkowite $n,m$, oznaczające odpowiednio liczbę żołnierzy i koszt pojedynczego ataku.

Kolejne $n$ wierszy zawiera po dwie liczby całkowite $a_i,b_i$, opisujące odpowiednio punkty życia i korzyść za każdego żołnierza.

Wyjście

Wynik należy zapisać do pliku soldier.out.

Dla każdego zestawu danych wypisz jeden wiersz z jedną liczbą całkowitą: największą możliwą sumą korzyści pomniejszoną o sumę kosztów spośród wszystkich planów.

Przykład

Wejście 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

Wyjście 1

12
6
7

Uwagi

W pierwszym zestawie danych jeden z optymalnych planów obejmuje trzy ataki na przedziały $[1,5]$, $[2,4]$ i $[4,4]$. Końcowy ciąg punktów życia to $(0,0,-1,0,4)$, korzyść wynosi $b_1+b_2+b_3+b_4=15$, a koszt to $3\times 1=3$. Można udowodnić, że nie istnieje lepszy plan, zatem wynikiem jest $15-3=12$.

W drugim zestawie danych jeden z optymalnych planów obejmuje dwa ataki na przedziały $[1,1]$ i $[3,3]$.

W trzecim zestawie danych jeden z optymalnych planów obejmuje jeden atak na przedział $[1,3]$.

Podzadania

Niech $\sum n$ oznacza sumę wartości $n$ ze wszystkich zestawów danych w jednym teście. Dla wszystkich danych testowych zagwarantowano:

• $1\le T\le 5\times 10^5$;

• $1\le n,\sum n\le 5\times 10^5$, $1\le m\le 10^9$;

• Dla każdego $1\le i\le n$: $1\le a_i\le 10^9$, $-10^9\le b_i\le 10^9$.