มีเมืองทั้งหมด $n$ เมือง สำหรับแต่ละเมือง $i$ เราจะกำหนดค่าให้และจ่ายราคาตามที่กำหนด กล่าวคือ หากกำหนดค่าเป็น $0$ เราจะจ่าย $p_i$ เหรียญ หรือหากกำหนดค่าเป็น $1$ เราจะจ่าย $q_i$ เหรียญ
นอกจากนี้ยังมีข้อจำกัดอีก $m$ ข้อ แต่ละข้อจำกัดถูกกำหนดโดยช่วง $[\ell, r]$ และค่าปรับสองค่าคือ $a$ และ $b$ หากมีเมืองอย่างน้อยหนึ่งเมืองที่มีค่าเป็น $0$ ในบรรดาเมืองตั้งแต่ $\ell$ ถึง $r$ (รวมขอบทั้งสองด้าน) เราจะต้องจ่ายค่าปรับ $a$ เหรียญ หากมีเมืองอย่างน้อยหนึ่งเมืองในนั้นที่มีค่าเป็น $1$ เราจะต้องจ่ายค่าปรับ $b$ เหรียญ ค่าปรับทั้งสองนี้เป็นอิสระต่อกัน กล่าวคือ หากมีทั้ง $0$ และ $1$ ปรากฏอยู่ เราจะต้องจ่าย $a + b$ เหรียญ
จงหาค่าใช้จ่ายรวมที่น้อยที่สุด (ราคาบวกค่าปรับ) จากทุกวิธีที่เป็นไปได้ในการเลือกค่าให้กับเมืองต่างๆ
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนเต็ม $t$: จำนวนชุดข้อมูลทดสอบ
บรรทัดแรกของแต่ละชุดข้อมูลทดสอบประกอบด้วยจำนวนเต็มสองจำนวนคือ $n$ และ $m$ ($1 \le n, m \le 2 \cdot 10^5$)
แต่ละบรรทัดใน $n$ บรรทัดถัดไปประกอบด้วยจำนวนเต็มสองจำนวนคือ $p_i$ และ $q_i$ ($1 \le p_i, q_i \le 10^9$): ค่าใช้จ่ายในการเลือก $0$ และ $1$ สำหรับเมือง $i$ ตามลำดับ
แต่ละบรรทัดใน $m$ บรรทัดถัดไปประกอบด้วยจำนวนเต็มสี่จำนวนคือ $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): พารามิเตอร์ของข้อจำกัด
ผลรวมของ $n$ จากทุกชุดข้อมูลทดสอบไม่เกิน $2 \cdot 10^5$
ผลรวมของ $m$ จากทุกชุดข้อมูลทดสอบไม่เกิน $2 \cdot 10^5$
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลจำนวนเต็มหนึ่งจำนวน คือค่าใช้จ่ายรวมที่น้อยที่สุด
ตัวอย่าง
ข้อมูลนำเข้า 1
2 3 2 1 5 5 1 3 3 1 3 10 10 2 2 100 1 1 1 7 8 1 1 1 1
ข้อมูลส่งออก 1
20 8