Aoi có \(N\) chiếc bánh. Bánh \(i\) có loại \(A_i\) và kích thước \(C_i\). Cô phải chọn đúng \(M\) bánh để mang đến nhà Bitaro.

Bitaro có \(M\) túi. Túi \(j\) chứa được nhiều nhất một bánh có loại đúng bằng \(B_j\) và kích thước không vượt quá \(D_j\). Sau khi Aoi chọn bánh, Bitaro xếp chúng vào túi để nhận được nhiều bánh nhất. Ngược lại, Aoi biết mọi thông tin về túi và chọn \(M\) bánh để số bánh Bitaro cuối cùng nhận được là nhỏ nhất.

Hãy tìm số bánh Bitaro nhận được khi cả hai đều chơi tối ưu.

Dữ liệu vào

Dòng đầu gồm \(N,M,T\). Có \(N\) dòng tiếp theo, dòng \(i\) gồm \(A_i,C_i\). Có \(M\) dòng sau đó, dòng \(j\) gồm \(B_j,D_j\).

Dữ liệu ra

In một số nguyên: số bánh Bitaro nhận được.

Ràng buộc

• \(1 ≤ N ≤ 500000\).
• \(1 ≤ M ≤ min(N,5000)\).
• \(1 ≤ T ≤ N\).
• \(1 ≤ A_i,B_j ≤ T\).
• \(1 ≤ C_i,D_j ≤ 10^9\).
• Mọi giá trị đầu vào là số nguyên.

Phân nhóm

1. \(12\) điểm: \(T=1\).
2. \(17\) điểm: \(N ≤ 10\).
3. \(9\) điểm: \(N=M=T\) và \(A_i=B_i=i\) với mọi \(i\).
4. \(36\) điểm: \(N ≤ 5000\).
5. \(26\) điểm: không có ràng buộc thêm.

Ví dụ

5 3 1
1 9
1 3
1 6
1 1
1 5
1 10
1 5
1 5

2

5 3 3
1 9
2 3
2 6
3 1
3 5
1 10
2 7
2 5

1

5 5 5
1 9
2 3
3 6
4 1
5 5
1 10
2 7
3 5
4 8
5 6

4

3 3 2
1 5
1 5
1 1
1 2
1 2
2 2

1

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 3, bài Packing Snacks.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.