توجد $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