$n$ soldats sont alignés. Initialement, le soldat numéro $i$ possède $a_i$ points de vie.

Vous pouvez effectuer plusieurs attaques, ou aucune. À chaque attaque, vous choisissez un intervalle $[l,r]$ avec $1\le l\le r\le n$ et diminuez de $1$ les points de vie de tous les soldats dont le numéro appartient à cet intervalle. Chaque attaque coûte $m$.

Après toutes les attaques, si le soldat numéro $i$ possède au plus $0$ point de vie, vous obtenez un gain de $b_i$. Les soldats mêlant ennemis et alliés, $b_i$ peut être négatif. Notez que le gain associé à chaque soldat ne peut être obtenu qu'une fois.

Vous devez trouver une stratégie d'attaque maximisant le total des gains moins le total des coûts. Formellement, supposons que votre stratégie effectue $k$ attaques et que le soldat numéro $i$ possède finalement $c_i$ points de vie. Posons $p_i=1$ si $c_i\le0$, et $p_i=0$ sinon. Vous devez maximiser $\left(\sum_{i=1}^{n}p_i\times b_i\right)-m\times k$. Il suffit de donner la valeur maximale du total des gains moins le total des coûts.

Entrée

Les données sont lues dans le fichier soldier.in.

Il y a plusieurs cas de test.

La première ligne contient un entier positif $T$, le nombre de cas de test.

Les cas de test sont ensuite donnés dans l'ordre. Pour chacun :

La première ligne contient deux entiers $n,m$, respectivement le nombre de soldats et le coût d'une attaque.

Chacune des $n$ lignes suivantes contient deux entiers $a_i,b_i$, décrivant respectivement les points de vie et le gain associés à un soldat.

Sortie

Écrivez dans le fichier soldier.out.

Pour chaque cas de test, écrivez une ligne contenant un entier : la valeur maximale, parmi toutes les stratégies possibles, du total des gains moins le total des coûts.

Exemples

Entrée 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

Sortie 1

12
6
7

Remarque

Dans le premier cas de test, une stratégie optimale consiste à effectuer trois attaques, sur les intervalles $[1,5]$, $[2,4]$ et $[4,4]$. La suite finale des points de vie est $(0,0,-1,0,4)$, le gain est $b_1+b_2+b_3+b_4=15$ et le coût est $3\times1=3$. On peut démontrer qu'aucune stratégie n'est meilleure. La sortie est donc $15-3=12$.

Dans le deuxième cas de test, une stratégie optimale consiste à effectuer deux attaques, sur les intervalles $[1,1]$ et $[3,3]$.

Dans le troisième cas de test, une stratégie optimale consiste à effectuer une attaque sur l'intervalle $[1,3]$.

Sous-tâches

Notons $\sum n$ la somme des valeurs de $n$ de tous les cas de test d'un même fichier de test. Pour toutes les données, on garantit :

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