Bài 4 (4,0 điểm; Đề TS vào 10 - Quảng Ngãi 2026 - 2027)

Trên tuyến đường từ Bắc vào Nam có n điểm được đánh số lần lượt 1, 2, ..., n. Dọc trên tuyến đường này có p trạm xăng đặt tại các điểm x₁, x₂, ..., x_p.

Hãng xe XYZ có m tuyến xe vận tải hành khách dọc theo tuyến đường này. Tuyến xe thứ i (1 ≤ i ≤ m) di chuyển từ điểm l_i tới điểm r_i và ngược lại. Để chuẩn bị tốt nhiên liệu cho các tuyến xe, hãng XYZ muốn biết có bao nhiêu tuyến xe không có trạm xăng nào được đặt trên tuyến đường mà nó đi qua.
Yêu cầu: Đếm số lượng các tuyến xe của hãng XYZ mà không có trạm xăng nào trên tuyến đường nó đi qua.

Dữ liệu vào: Từ tệp văn bản BAI4.INP có cấu trúc:

• Dòng thứ nhất chứa 3 số nguyên dương lần lượt là n, m, p (n ≤ 10⁶, 1 ≤ m, p ≤ 10⁵).
• Dòng thứ i trong m dòng tiếp theo chứa 2 số nguyên dương lần lượt là l_i, r_i mô tả tuyến xe thứ i (1 ≤ l_i < r_i ≤ n, 1 ≤ i ≤ m).
• Dòng cuối cùng chứa p số nguyên dương x₁, x₂, ..., x_p (1 ≤ x_i ≤ n, 1 ≤ i ≤ p). Các số trên cùng một dòng cách nhau bởi dấu cách.

Dữ liệu ra: Ghi vào tệp văn bản BAI4.OUT có cấu trúc:

• Ghi một số nguyên là kết quả thỏa mãn yêu cầu bài toán.

Ví dụ:

Giới hạn:

• Subtask 1 (30% số điểm): Có 30% test với p = 1, m ≤ 10³.
• Subtask 2 (40% số điểm): Có 40% test với m, p ≤ 10³.
• Subtask 3 (30% số điểm): Có 30% test với m, p ≤ 10⁵.