יש $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$, ו-$p_i=0$ אחרת. עליך למקסם את $\left(\sum_{i=1}^{n}p_i\times b_i\right)-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$;
• $\forall 1\le i\le n$, $1\le a_i\le10^9$, $-10^9\le b_i\le10^9$.