Lưu ý: Giới hạn thời gian của bài này là 4 giây, bằng 2 lần giới hạn mặc định.

Farmer John đã phân bố bò và kiện hàng theo một quy luật kỳ lạ trên trục số bằng quy trình sau:

• Farmer John chọn một số \(M\) (\(1\le M\le 10^{18}\)).
• Farmer John chọn \(N\) (\(1\le N\le 2\cdot 10^4\)) đoạn \([L_i,R_i]\) để phân bố bò (\(1\le L_i\le R_i\le 10^{18}\)). Sau đó, ông đặt bò tại các vị trí \(L_i,L_i+M,L_i+2M,\ldots,R_i\). Đảm bảo \(R_i-L_i\) là bội của \(M\).
• Farmer John chọn \(P\) (\(1\le P\le 2\cdot 10^4\)) đoạn \([A_i,B_i]\) để phân bố kiện hàng (\(1\le A_i\le B_i\le 10^{18}\)). Sau đó, ông đặt các kiện hàng tại các vị trí \(A_i,A_i+M,A_i+2M,\ldots,B_i\). Đảm bảo \(B_i-A_i\) là bội của \(M\).

Sau khi bò và kiện hàng được phân bố, Farmer John muốn biết các con bò mất bao lâu để nhặt các kiện hàng. Mỗi giây, bằng chiếc bộ đàm tiện dụng của mình, Farmer John có thể ra lệnh cho một con bò duy nhất di chuyển một đơn vị sang trái hoặc sang phải so với vị trí hiện tại. Nếu một con bò đi đến vị trí có một kiện hàng, nó có thể nhặt kiện hàng đó. Farmer John muốn biết số giây ít nhất cần thiết để các con bò nhặt hết mọi kiện hàng.

Dữ liệu vào

Dòng đầu tiên chứa \(M\), \(N\) và \(P\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\).

\(P\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A_i\) và \(B_i\).

Dữ liệu ra

In ra một số nguyên, biểu thị thời gian nhỏ nhất để các con bò có thể nhặt hết mọi kiện hàng, với điều kiện mỗi giây ông chỉ có thể ra một lệnh sang trái/phải cho một con bò duy nhất.

Ví dụ

100 3 7
10 10
20 20
30 30
7 7
11 11
13 13
17 17
24 24
26 26
33 33

22

2 1 1
1 5
2 6

3

Phân nhóm

• Dữ liệu 3–4: Đảm bảo tổng số bò và kiện hàng không vượt quá \(2\cdot 10^5\).
• Dữ liệu 5–10: Đảm bảo \(N,P\le 500\).
• Dữ liệu 11–13: Đảm bảo không có hai đoạn phân bố kiện hàng hoặc bò nào giao nhau.
• Dữ liệu 14–20: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar và Benjamin Qi.

Nguồn

USACO 2025 US Open Contest, Platinum — Package Pickup: https://usaco.org/index.php?page=viewproblem2&cpid=1526