Có $n$ người lính đứng thành một hàng. Ban đầu, người lính mang số $i$ có lượng máu $a_i$.

Bạn có thể thực hiện một số lần tấn công (cũng có thể không tấn công lần nào). Trong mỗi lần tấn công, bạn chọn một đoạn $[l,r]$ với $1\le l\le r\le n$, rồi giảm lượng máu của mỗi người lính có số hiệu thuộc đoạn đó đi $1$. Mỗi lần tấn công tốn chi phí $m$.

Sau khi mọi lần tấn công kết thúc, nếu lượng máu của người lính thứ $i$ không vượt quá $0$, bạn nhận được lợi ích $b_i$. Vì trong hàng lính có cả địch lẫn ta, $b_i$ có thể âm. Lưu ý rằng lợi ích từ mỗi người lính chỉ được nhận một lần.

Bạn cần tìm một phương án tấn công để tối đa hóa tổng lợi ích trừ tổng chi phí. Cụ thể, giả sử phương án của bạn thực hiện $k$ lần tấn công và lượng máu cuối cùng của người lính thứ $i$ là $c_i$. Đặt $p_i$ bằng $1$ nếu $c_i\le0$, và bằng $0$ nếu không. Bạn cần tối đa hóa $(\sum_{i=1}^n p_i\times b_i)-m\times k$. Cuối cùng, bạn chỉ cần đưa ra giá trị lớn nhất của tổng lợi ích trừ tổng chi phí.

Dữ liệu vào

Bài này có nhiều bộ dữ liệu kiểm tra.

Dòng đầu tiên chứa một số nguyên dương $T$, cho biết số bộ dữ liệu.

Tiếp theo là lần lượt các bộ dữ liệu. Với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên $n,m$, lần lượt là số người lính và chi phí cho một lần tấn công.

Tiếp theo là $n$ dòng, mỗi dòng chứa hai số nguyên $a_i,b_i$, lần lượt mô tả lượng máu và lợi ích của mỗi người lính.

Dữ liệu ra

Với mỗi bộ dữ liệu, in một dòng chứa một số nguyên: giá trị lớn nhất của tổng lợi ích trừ tổng chi phí trong tất cả các phương án có thể.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

12
6
7

Ghi chú

Trong bộ dữ liệu thứ nhất, một phương án tối ưu là tấn công ba lần, lần lượt chọn các đoạn $[1,5],[2,4],[4,4]$. Dãy lượng máu cuối cùng là $(0,0,-1,0,4)$, lợi ích là $b_1+b_2+b_3+b_4=15$, còn chi phí là $3\times1=3$. Có thể chứng minh rằng không có phương án nào tốt hơn, nên kết quả là $15-3=12$.

Trong bộ dữ liệu thứ hai, một phương án tối ưu là tấn công hai lần, lần lượt chọn các đoạn $[1,1],[3,3]$.

Trong bộ dữ liệu thứ ba, một phương án tối ưu là tấn công một lần, chọn đoạn $[1,3]$.

Nhiệm vụ con

Gọi $\sum n$ là tổng các giá trị $n$ của mọi bộ dữ liệu trong một tệp kiểm tra. Với mọi bộ dữ liệu, đảm bảo:

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