Universal Cup Judging System

Universal Cup

Time Limit: 1 s Memory Limit: 1024 MB
Statistics

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.