Đất nước IOI quyết định xây dựng đồng bộ mạng lưới giao thông. Đất nước được biểu diễn trên mặt phẳng tọa độ \(xy\), với \(N\) thị trấn. Thị trấn thứ \(i\) nằm tại \((X_i,Y_i)\).

Việc xây dựng gồm hai phần:

• Chọn một số thị trấn để xây sân bay quốc tế. Phải xây ít nhất một sân bay. Mỗi sân bay có một chi phí xây dựng cố định.
• Xây một số con đường nối các thị trấn. Mỗi đường là một đoạn thẳng nối trực tiếp hai điểm biểu diễn hai thị trấn và song song với trục \(x\) hoặc trục \(y\). Chi phí xây mỗi đường bằng độ dài của nó.

Có \(M\) khu vực không thể xây đường, chẳng hạn do nền đất yếu. Khu vực thứ \(j\) là hình chữ nhật có góc dưới bên trái tại \((P_j,Q_j)\) và góc trên bên phải tại \((R_j,S_j)\), với \(P_j<R_j\) và \(Q_j<S_j\). Mỗi khu vực bao gồm cả phần biên. Không con đường nào được có điểm chung với bất kỳ khu vực cấm nào, kể cả biên của khu vực đó.

Sau khi xây dựng, từ mỗi thị trấn phải có thể đến một thị trấn có sân bay quốc tế bằng cách đi theo các con đường từ thị trấn này sang thị trấn khác.

Có \(C\) công ty xây dựng đang được xem xét để giao toàn bộ dự án. Công ty thứ \(k\) cần chi phí \(B_k\) cho mỗi sân bay và có thể xây tối đa \(H_k\) sân bay. Chi phí xây đường không phụ thuộc công ty; không có giới hạn về số lượng hay độ dài các con đường.

Với mỗi công ty, cần tìm tổng chi phí nhỏ nhất để đáp ứng các điều kiện trên. Một công ty có thể không thực hiện được dự án do giới hạn số sân bay quá thấp.

Yêu cầu

Cho tọa độ các thị trấn, các khu vực cấm xây đường và thông tin các công ty, hãy tính tổng chi phí nhỏ nhất nếu giao dự án cho từng công ty, hoặc xác định rằng công ty đó không thể thực hiện dự án.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa ba số nguyên \(N,M,C\), lần lượt là số thị trấn, số khu vực cấm xây đường và số công ty.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), là tọa độ thị trấn thứ \(i\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa bốn số nguyên \(P_j,Q_j,R_j,S_j\), mô tả khu vực cấm thứ \(j\).
• Trong \(C\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(B_k,H_k\), là chi phí xây một sân bay và số sân bay tối đa của công ty thứ \(k\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(C\) dòng. Dòng thứ \(k\) chứa tổng chi phí nhỏ nhất nếu công ty thứ \(k\) thực hiện dự án. Nếu công ty đó không thể đáp ứng các điều kiện, ghi -1.

Ràng buộc

• Giới hạn thời gian: 5 giây.
• Giới hạn bộ nhớ: 256 MB.
• \(1\le N\le200000\).
• \(1\le M\le200000\).
• \(1\le C\le500000\).
• \(0\le X_i,Y_i\le10^9\).
• Không có hai thị trấn trùng tọa độ.
• \(0\le P_j<R_j\le10^9\) và \(0\le Q_j<S_j\le10^9\).
• Không thị trấn nào nằm trong hoặc trên biên của bất kỳ khu vực cấm nào.
• \(1\le B_k\le10^9\) và \(1\le H_k\le N\).

Phân nhóm

Mỗi nhóm gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm.

• Nhóm 1 (10 điểm): \(M\le100\), \(C\le100\).
• Nhóm 2 (30 điểm): \(C\le100\).
• Nhóm 3 (30 điểm): \(M\le100\).
• Nhóm 4 (30 điểm): Không có ràng buộc bổ sung.

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

28
38
-1

Có thể xây đường nối thị trấn \(2\) với \(4\) và thị trấn \(3\) với \(4\). Không thể xây đường nối thị trấn \(1\) với \(2\) vì đường đó đi qua khu vực cấm. Cũng không thể xây đường nối thị trấn \(1\) với \(3\), vì đường không được có điểm chung ngay cả với biên của khu vực cấm.

• Công ty thứ nhất xây được tối đa \(4\) sân bay với chi phí \(7\) mỗi sân bay. Phương án tốt nhất là xây sân bay tại cả bốn thị trấn và không xây đường nào, với tổng chi phí \(7\times4=28\).
• Công ty thứ hai xây được tối đa \(3\) sân bay với chi phí \(10\) mỗi sân bay. Một phương án tốt nhất là xây hai đường dài \(9\) nối \(2\) với \(4\) và \(3\) với \(4\), rồi xây sân bay ở thị trấn \(1\) và \(2\). Tổng chi phí là \(10\times2+9+9=38\).
• Công ty thứ ba chỉ xây được tối đa một sân bay với chi phí \(1\). Do không thể xây đường nối thị trấn \(1\) với bất kỳ thị trấn nào khác, dự án cần ít nhất hai sân bay. Công ty này không thể thực hiện dự án, nên kết quả là -1.