Há $n$ soldados em uma fila. Inicialmente, o soldado de número $i$ tem $a_i$ pontos de vida.

Você pode realizar vários ataques (ou nenhum). Em cada ataque, pode escolher um intervalo $[l,r]$ ($1\le l\le r\le n$) e reduzir em $1$ a vida de todos os soldados cujos números pertencem a esse intervalo. Cada ataque tem custo $m$.

Depois de todos os ataques, se a vida do soldado $i$ for menor ou igual a $0$, você receberá uma recompensa $b_i$. Como há inimigos e aliados misturados entre os soldados, $b_i$ pode ser negativo. Observe que a recompensa de cada soldado é recebida apenas uma vez.

Você deve encontrar um plano de ataques que maximize a soma das recompensas menos a soma dos custos. Formalmente, suponha que seu plano realize $k$ ataques e que a vida final do soldado $i$ seja $c_i$. Defina $p_i$ como $1$ se $c_i\le0$ e como $0$ caso contrário. Você deve maximizar $(\sum_{i=1}^{n}p_i\times b_i)-m\times k$. Basta fornecer o maior valor possível da soma das recompensas menos a soma dos custos.

Entrada

Leia os dados do arquivo soldier.in.

Este problema contém vários casos de teste.

A primeira linha da entrada contém um inteiro positivo $T$, que indica a quantidade de casos de teste.

Em seguida, cada caso de teste é apresentado da seguinte forma:

A primeira linha contém dois inteiros $n,m$, que indicam, respectivamente, a quantidade de soldados e o custo de um ataque.

As próximas $n$ linhas contêm dois inteiros $a_i,b_i$ cada, que descrevem a vida e a recompensa de cada soldado.

Saída

Escreva a saída no arquivo soldier.out.

Para cada caso de teste, imprima uma linha com um inteiro: o maior valor da soma das recompensas menos a soma dos custos entre todos os planos possíveis.

Exemplos

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

Saída 1

12
6
7

Explicação

No primeiro caso de teste, um plano ótimo consiste em realizar três ataques, escolhendo os intervalos $[1,5]$, $[2,4]$ e $[4,4]$. A sequência final de pontos de vida é $(0,0,-1,0,4)$, a recompensa é $b_1+b_2+b_3+b_4=15$ e o custo é $3\times1=3$. Pode-se provar que não existe plano melhor; portanto, a saída é $15-3=12$.

No segundo caso de teste, um plano ótimo consiste em realizar dois ataques, escolhendo os intervalos $[1,1]$ e $[3,3]$.

No terceiro caso de teste, um plano ótimo consiste em realizar um ataque, escolhendo o intervalo $[1,3]$.

Subtarefas

Seja $\sum n$ a soma dos valores de $n$ de todos os casos de teste em um único arquivo de teste. Para todos os dados de teste, garante-se que:

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