Universal Cup Judging System

Universal Cup

実行時間制限: 1 s メモリ制限: 1024 MB
統計

Có $n$ thành phố. Đối với mỗi thành phố $i$, chúng ta gán một giá trị và trả chi phí tương ứng: hoặc giá trị là $0$ và chúng ta trả $p_i$ đồng xu, hoặc giá trị là $1$ và chúng ta trả $q_i$ đồng xu.

Ngoài ra, có $m$ ràng buộc được cho. Một ràng buộc được xác định bởi một đoạn $[\ell, r]$ và hai mức phạt $a$ và $b$. Nếu có ít nhất một thành phố mang giá trị $0$ trong số các thành phố từ $\ell$ đến $r$ (tính cả hai đầu mút), chúng ta phải trả khoản phạt $a$ đồng xu. Nếu có ít nhất một thành phố mang giá trị $1$ trong số đó, chúng ta phải trả khoản phạt $b$ đồng xu. Hai khoản phạt này độc lập với nhau: nếu cả $0$ và $1$ đều xuất hiện, chúng ta phải trả $a + b$ đồng xu.

Hãy tìm tổng chi phí nhỏ nhất (bao gồm chi phí gán giá trị cộng với tiền phạt) trong tất cả các cách chọn giá trị cho các thành phố.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$: số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n$ và $m$ ($1 \le n, m \le 2 \cdot 10^5$).

Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $p_i$ và $q_i$ ($1 \le p_i, q_i \le 10^9$): chi phí tương ứng khi chọn $0$ và $1$ cho thành phố $i$.

Mỗi dòng trong $m$ dòng tiếp theo chứa bốn số nguyên $\ell$, $r$, $a$, $b$ ($1 \le \ell \le r \le n$, $1 \le a, b \le 10^9$): các tham số của một ràng buộc.

Tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Tổng của $m$ trong tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một số nguyên: tổng chi phí nhỏ nhất.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 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.