มีทหาร $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$