Sữa hỏng

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ người và $M$ loại sữa. Một trong các loại sữa đã bị hỏng — ai uống sữa hỏng sẽ bị bệnh.

Cho $D$ sự kiện uống sữa, mỗi sự kiện ghi lại người $p$ uống sữa loại $m$ tại thời điểm $t$ . Cho $S$ sự kiện bệnh, mỗi sự kiện ghi lại người $p$ bị bệnh tại thời điểm $t$ .

Một loại sữa có thể là sữa hỏng nếu mọi người bị bệnh đều đã uống loại sữa đó trước khi bị bệnh (tức là uống tại thời điểm $< t$ bệnh).

Với mỗi loại sữa có thể là sữa hỏng, đếm số người đã uống loại sữa đó. Hãy tìm số lượng thuốc tối thiểu cần chuẩn bị để đảm bảo chữa cho tất cả mọi người có thể bị bệnh trong trường hợp xấu nhất.

Dữ liệu vào

Dòng đầu: bốn số nguyên $N$ , $M$ , $D$ , $S$ .
$D$ dòng tiếp theo: ba số nguyên $p$ , $m$ , $t$ — người $p$ uống sữa $m$ tại thời điểm $t$ .
$S$ dòng tiếp theo: hai số nguyên $p$ , $t$ — người $p$ bị bệnh tại thời điểm $t$ .

Dữ liệu ra

Một số nguyên duy nhất — số thuốc cần chuẩn bị (giá trị lớn nhất trong số người uống mỗi loại sữa nghi ngờ).

Ràng buộc

$1 \leq N \leq 50$
$1 \leq M \leq 50$
$1 \leq D \leq 1000$
$1 \leq S \leq N$
$1 \leq t \leq 100$

Ví dụ

Input	Output	Giải thích
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	Sữa loại $1$ có thể là sữa hỏng (cả người 1 và 2 đều uống trước khi bệnh). Có 3 người đã uống sữa loại 1.

Bình luận

Không có bình luận tại thời điểm này.