以其农场生产的牛奶质量而闻名的农夫约翰正在为 N 个他最好的朋友举办一次牛奶品尝会。
不幸的是,在聚会上提供的 M 种牛奶中,恰好有一种变质了,可约翰却不知道是哪一种!
任何喝了劣质牛奶的人都会在之后的某个时间生病,也许在聚会期间,也许在聚会结束之后。
你会得到一份聚会的记录----记载整个聚会期间何人何时喝酒以及何人何时生病。
根据这些信息,你可以推断出哪些牛奶可能是劣质牛奶。
利用这些获知,帮助约翰确定他将需要准备的最小剂量的药物,以确保他可以在聚会期间或聚会之后治愈所有患病的人。
第一行包含四个整数 N,M,D,S。
接下来 D 行,每行包含三个整数 p,m,t,表示客人 p 在时间 t 喝了牛奶 m。
一个人可能在多个时间点喝了同一种牛奶,也可能在同一时间点喝了多种牛奶。
接下来 S 行,每行包含两个整数 p,t,表示客人 p 在时间 t 生病。
一个人最多只能生一次病,而且生病原因一定是在生病前某个时间点喝了劣质牛奶。
输出一个整数,表示约翰需要准备的最小药物剂量,以便他可以保证他将有足够的剂量来治疗所有在聚会期间和之后患病的人。
1≤N,M≤50,
1≤D≤1000,
1≤S≤N,
1≤p≤N,
1≤m≤M,
1≤t≤100
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
此样例中,共 3 个人和 4 种牛奶。
客人 1 在时间 3 生病,客人 2 在时间 8 生病,客人 3 在聚会上没有生病,但是不能排除他在聚会结束后生病的可能性。
现在,我们逐个考虑每种牛奶,看看它们中哪些可能受到污染。
我们可以知道,一个生病的人在生病前如果喝了某种牛奶,那么这种牛奶就有可能是劣质牛奶。
牛奶 1:两个患病的客人(1 和 2)在生病前都喝过这种牛奶,所以它有可能是劣质牛奶。如果情况属实,那么由于第 3 个人也喝过它,所以会有 3 人患病(客人 3 在聚会之后得病)。
牛奶 2:两个患病的客人(1 和 2)在生病前都喝过这种牛奶,所以它有可能是劣质牛奶。如果情况属实,那么由于第 3 个人没喝过它,所以会有 2 人患病。
牛奶 3:这一定不是劣质牛奶,因为客人 1 在生病之前没有喝过它。
牛奶 4:这一定不是劣质牛奶,因为客人 2 没喝过它。
因此,约翰至少需要准备 3 份药物,才能确保所有人都能被治愈,不论劣质牛奶是 1 还是 2。