Hay $n$ soldados en fila. Inicialmente, el soldado con número $i$ tiene $a_i$ puntos de vida.

Puedes realizar varios ataques, o ninguno. En cada ataque puedes elegir un intervalo $[l,r]$ ($1\le l\le r\le n$) y reducir en $1$ la vida de todos los soldados cuyos números pertenecen a ese intervalo. Cada ataque cuesta $m$.

Después de todos los ataques, si la vida del soldado $i$ es como máximo $0$, obtienes un beneficio de $b_i$. Como entre los soldados hay tanto amigos como enemigos, $b_i$ puede ser negativo. Ten en cuenta que el beneficio de cada soldado se obtiene una sola vez.

Debes encontrar un plan de ataques que maximice la suma de los beneficios menos la suma de los costes. Formalmente, supongamos que tu plan realiza $k$ ataques y que la vida final del soldado $i$ es $c_i$. Sea $p_i=1$ si $c_i\le0$, y $p_i=0$ en caso contrario. Debes maximizar $(\sum_{i=1}^{n}p_i\times b_i)-m\times k$. Solo debes indicar el valor máximo de la suma de beneficios menos la suma de costes.

Entrada

Los datos se leen del archivo soldier.in.

Esta tarea contiene varios casos de prueba.

La primera línea de la entrada contiene un entero positivo $T$, el número de casos de prueba.

A continuación se dan los casos de prueba en orden. Para cada caso:

La primera línea contiene dos enteros $n,m$, que representan el número de soldados y el coste de cada ataque, respectivamente.

Las siguientes $n$ líneas contienen dos enteros $a_i,b_i$ cada una, que describen la vida y el beneficio de cada soldado, respectivamente.

Salida

Escribe en el archivo soldier.out.

Para cada caso, escribe una línea con un entero: el mayor valor posible de la suma de beneficios menos la suma de costes entre todos los planes posibles.

Ejemplos

Entrada 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

Salida 1

12
6
7

Nota

En el primer caso, un plan óptimo consiste en realizar tres ataques sobre los intervalos $[1,5]$, $[2,4]$ y $[4,4]$, respectivamente. La secuencia final de vida es $(0,0,-1,0,4)$, el beneficio es $b_1+b_2+b_3+b_4=15$ y el coste es $3\times1=3$. Se puede demostrar que no existe un plan mejor, por lo que se escribe $15-3=12$.

En el segundo caso, un plan óptimo consiste en realizar dos ataques sobre los intervalos $[1,1]$ y $[3,3]$, respectivamente.

En el tercer caso, un plan óptimo consiste en realizar un ataque sobre el intervalo $[1,3]$.

Subtareas

Sea $\sum n$ la suma de los valores de $n$ de todos los casos de prueba de un mismo archivo de prueba. Para todos los datos se garantiza:

• $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$.