Ada $n$ prajurit yang berdiri berjajar. Awalnya, prajurit bernomor $i$ memiliki darah sebesar $a_i$.

Anda dapat melakukan beberapa serangan, atau tidak melakukan serangan sama sekali. Pada setiap serangan, Anda dapat memilih sebuah interval $[l,r]\ (1\le l\le r\le n)$ dan mengurangi darah setiap prajurit yang nomornya berada dalam interval tersebut sebesar $1$. Setiap serangan memerlukan biaya sebesar $m$.

Setelah semua serangan selesai, jika darah prajurit ke-$i$ tidak lebih dari $0$, Anda memperoleh keuntungan sebesar $b_i$. Karena di antara para prajurit terdapat campuran kawan dan lawan, $b_i$ dapat bernilai negatif. Perhatikan bahwa keuntungan dari setiap prajurit hanya diperoleh satu kali.

Anda harus menemukan rencana serangan yang memaksimalkan total keuntungan dikurangi total biaya. Secara formal, misalkan rencana Anda melakukan $k$ serangan dan darah akhir prajurit ke-$i$ adalah $c_i$. Definisikan $p_i$ bernilai $1$ jika $c_i\le0$, dan $0$ jika tidak. Maka Anda harus memaksimalkan $(\sum_{i=1}^n p_i\times b_i)-m\times k$. Anda hanya perlu memberikan nilai maksimum total keuntungan dikurangi total biaya.

Masukan

Baca data dari berkas soldier.in.

Soal ini memiliki beberapa kasus uji.

Baris pertama masukan berisi sebuah bilangan bulat positif $T$ yang menyatakan jumlah kasus uji.

Selanjutnya, setiap kasus uji diberikan secara berurutan. Untuk setiap kasus uji:

Baris pertama berisi dua bilangan bulat $n,m$, masing-masing menyatakan jumlah prajurit dan biaya satu serangan.

Selanjutnya terdapat $n$ baris, masing-masing berisi dua bilangan bulat $a_i,b_i$, yang menyatakan darah dan keuntungan setiap prajurit.

Keluaran

Tulis keluaran ke berkas soldier.out.

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat yang menyatakan nilai maksimum total keuntungan dikurangi total biaya yang dapat diperoleh dari semua rencana yang mungkin.

Contoh

Masukan 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

Keluaran 1

12
6
7

Penjelasan

Pada kasus uji pertama, salah satu rencana optimal adalah melakukan tiga serangan pada interval $[1,5],[2,4],[4,4]$. Urutan darah akhirnya adalah $(0,0,-1,0,4)$, keuntungannya $b_1+b_2+b_3+b_4=15$, dan biayanya $3\times1=3$. Dapat dibuktikan bahwa tidak ada rencana yang lebih baik, sehingga keluarannya adalah $15-3=12$.

Pada kasus uji kedua, salah satu rencana optimal adalah melakukan dua serangan pada interval $[1,1],[3,3]$.

Pada kasus uji ketiga, salah satu rencana optimal adalah melakukan satu serangan pada interval $[1,3]$.

Subsoal

Misalkan $\sum n$ menyatakan jumlah nilai $n$ dari semua kasus uji dalam satu berkas pengujian. Untuk semua kasus uji, dijamin bahwa:

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