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