ישנן $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