يقف $n$ جنديًا في صف. في البداية، تكون نقاط حياة الجندي ذي الرقم $i$ مساوية لـ$a_i$.

يمكنك تنفيذ عدد من الهجمات (ويمكنك أيضًا عدم تنفيذ أي هجوم). في كل هجوم، يمكنك اختيار فترة $[l,r]$ حيث $1\le l\le r\le n$، وتقليل نقاط حياة كل جندي رقمه ضمن هذه الفترة بمقدار $1$. تكلفة كل هجوم هي $m$.

بعد انتهاء جميع الهجمات، إذا كانت نقاط حياة الجندي ذي الرقم $i$ لا تتجاوز $0$، تحصل على عائد قدره $b_i$. وبما أن الجنود يتضمنون أصدقاء وأعداء، فقد يكون $b_i$ سالبًا. لاحظ أن عائد كل جندي يُحصَل عليه مرة واحدة فقط.

عليك إيجاد خطة هجوم تعظّم مجموع العوائد ناقص مجموع التكاليف. رسميًا، افترض أن خطتك تتضمن $k$ هجمات، وأن نقاط حياة الجندي ذي الرقم $i$ في النهاية هي $c_i$. ولتكن $p_i$ مساوية لـ$1$ عندما $c_i\le0$، ومساوية لـ$0$ خلاف ذلك. إذن عليك تعظيم $(\sum_{i=1}^{n}p_i\times b_i)-m\times k$. والمطلوب في النهاية هو إخراج أكبر قيمة لمجموع العوائد ناقص مجموع التكاليف فقط.

الإدخال

تُقرأ البيانات من الملف soldier.in.

يتضمن هذا السؤال عدة حالات اختبار.

يحتوي السطر الأول من الإدخال على عدد صحيح موجب $T$ يمثل عدد حالات الاختبار.

تُعطى بعد ذلك حالات الاختبار بالتتابع. لكل حالة اختبار:

يحتوي السطر الأول على عددين صحيحين $n,m$ يمثلان، على الترتيب، عدد الجنود وتكلفة الهجوم الواحد.

تلي ذلك $n$ أسطر، يحتوي كل منها على عددين صحيحين $a_i,b_i$ يصفان، على الترتيب، نقاط حياة كل جندي والعائد منه.

الإخراج

تُكتب النتيجة إلى الملف soldier.out.

لكل حالة اختبار، أخرج سطرًا يحتوي على عدد صحيح يمثل أكبر قيمة يمكن الحصول عليها لمجموع العوائد ناقص مجموع التكاليف، من بين جميع الخطط الممكنة.

أمثلة

الإدخال 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

الإخراج 1

12
6
7

ملاحظة

في حالة الاختبار الأولى، تتضمن إحدى الخطط المثلى تنفيذ ثلاث هجمات باختيار الفترات $[1,5],[2,4],[4,4]$ على الترتيب. يصبح تسلسل نقاط الحياة في النهاية $(0,0,-1,0,4)$، ويكون العائد $b_1+b_2+b_3+b_4=15$، والتكلفة $3\times1=3$. يمكن إثبات عدم وجود خطة أفضل، ولذلك يكون الإخراج $15-3=12$.

في حالة الاختبار الثانية، تتضمن إحدى الخطط المثلى تنفيذ هجومين باختيار الفترتين $[1,1],[3,3]$ على الترتيب.

في حالة الاختبار الثالثة، تتضمن إحدى الخطط المثلى تنفيذ هجوم واحد باختيار الفترة $[1,3]$.

المهام الفرعية

لتكن $\sum n$ مجموع قيم $n$ لجميع حالات الاختبار ضمن اختبار واحد. في جميع بيانات الاختبار، يُضمن ما يلي:

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