Farmer John, vốn nổi tiếng gần xa vì chất lượng sữa được sản xuất tại trang trại của mình, đang tổ chức một buổi thử sữa cho \(N\) người bạn thân nhất (\(1\le N\le50\)). Đáng tiếc là trong số \(M\) loại sữa có tại buổi tiệc (\(1\le M\le50\)), đúng một loại đã bị hỏng, nhưng Farmer John không biết đó là loại nào! Bất kỳ ai uống phải sữa hỏng sau đó sẽ bị ốm, có thể trong thời gian còn lại của buổi tiệc hoặc sau khi buổi tiệc kết thúc.

Bạn được cung cấp bản ghi của buổi tiệc — ai uống gì vào lúc nào, cũng như ai bị ốm vào lúc nào. Dựa vào thông tin này, bạn có thể suy ra những loại sữa nào có khả năng là loại bị hỏng. Dùng kết quả đó, hãy giúp Farmer John xác định số liều thuốc tối thiểu ông cần chuẩn bị để đảm bảo có thể chữa cho tất cả những người bị ốm, dù họ bị ốm trong hay sau buổi tiệc.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\), \(M\), \(D\) và \(S\).

\(D\) dòng tiếp theo (\(1\le D\le1000\)), mỗi dòng chứa ba số nguyên \(p,m,t\), cho biết người \(p\) đã uống loại sữa \(m\) tại thời điểm \(t\). Giá trị \(p\) nằm trong đoạn \(1\ldots N\), \(m\) nằm trong đoạn \(1\ldots M\) và \(t\) nằm trong đoạn \(1\ldots100\). Một người có thể uống cùng một loại sữa nhiều lần và cũng có thể uống nhiều loại sữa tại cùng một thời điểm.

\(S\) dòng tiếp theo (\(1\le S\le N\)), mỗi dòng chứa hai số nguyên \(p,t\), cho biết người \(p\) bị ốm tại thời điểm \(t\). Giá trị \(p\) nằm trong đoạn \(1\ldots N\) và \(t\) nằm trong đoạn \(1\ldots100\). Mỗi người bị ốm nhiều nhất một lần, và họ chỉ bị ốm vì đã uống sữa hỏng tại một thời điểm sớm hơn một cách nghiêm ngặt.

Dữ liệu ra

In một số nguyên duy nhất là số liều thuốc tối thiểu Farmer John cần chuẩn bị để đảm bảo có đủ liều chữa cho tất cả những người bị ốm, cả trong và sau buổi tiệc.

Ví dụ

3 4 7 2
1 1 1
1 4 1
1 3 4
1 2 2
3 1 3
2 1 5
2 2 7
1 3
2 8

3

Nguồn

USACO 2015 December Contest, Bronze - Contaminated Milk: https://usaco.org/index.php?page=viewproblem2&cpid=569

Tác giả: Austin Anderson và Brian Dean.