มนุษย์ต่างดาวจากอวกาศได้บุกโลกแล้ว (ในที่สุด!) จงป้องกันตัว มิฉะนั้นจะถูกสลายร่าง! หรือถูกกลืนเป็นพวกเดียวกัน หรือถูกกิน เรายังไม่แน่ใจ

มนุษย์ต่างดาวโจมตีตามรูปแบบที่ทราบอยู่แล้ว มีผู้โจมตี $n$ ตัว ตัวที่ $i$ ปรากฏในเวลา $a_i$ ที่ระยะห่าง $d_i$ จากคุณ ต้องทำลายมันไม่ช้ากว่าเวลา $b_i$ มิฉะนั้นมันจะยิงอาวุธ ซึ่งจะทำให้การต่อสู้จบลงอย่างแน่นอน

อาวุธของคุณคือปืนระเบิดพื้นที่ ซึ่งตั้งพลังได้ตามต้องการ เมื่อยิงด้วยพลัง $R$ จะทำลายมนุษย์ต่างดาวทั้งหมดที่อยู่ห่างไม่เกิน $R$ ทันที และใช้เซลล์เชื้อเพลิง $R$ เซลล์

จงหาค่าใช้จ่ายน้อยที่สุด (วัดเป็นจำนวนเซลล์เชื้อเพลิง) ในการทำลายมนุษย์ต่างดาวทั้งหมดโดยที่คุณไม่ถูกฆ่า

ขนาดไฟล์ข้อมูลนำเข้าไม่เกิน 0.1 MiB

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนกรณีทดสอบ $T$ จากนั้นเป็นรายละเอียดของแต่ละกรณีทดสอบ:

แต่ละกรณีเริ่มด้วยบรรทัดที่มีจำนวนมนุษย์ต่างดาว $n$ ($1 \le n \le 300$) ใน $n$ บรรทัดถัดไป บรรทัดที่ $i$ มีจำนวนเต็มสามจำนวน $a_i$, $b_i$, $d_i$ ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 10\,000$) มนุษย์ต่างดาวตัวที่ $i$ ปรากฏในเวลา $a_i$ ไม่ทำอะไรจนถึง $b_i$ และอยู่ห่างจากคุณ $d_i$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์หนึ่งบรรทัดที่มีจำนวนเซลล์น้อยที่สุดที่จำเป็นในการทำลายมนุษย์ต่างดาวทั้งหมด

ตัวอย่าง

ข้อมูลนำเข้า 1

1
3
1 4 4
4 7 5
3 4 7

ข้อมูลส่งออก 1

7