问题描述

农夫约翰举办牛奶品尝会，邀请N位好友品尝M种牛奶。其中恰好一种牛奶变质，饮用者会在之后生病（可能在聚会期间或之后）。给出聚会记录：

• 谁在什么时间喝了哪种牛奶
• 谁在什么时间生病

请确定：

1. 哪些牛奶可能是变质的
2. 农夫约翰需要准备的最少药剂剂量（确保能治疗所有可能生病的人）

输入格式

• 第一行：N M D S
• 接下来D行：p m t（人物p在时间t喝了牛奶m）
• 接下来S行：p t（人物p在时间t生病）

输出格式

需要准备的最少药剂剂量

输入样例

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

样例解释

可能变质的牛奶：

1. 牛奶1：所有生病者（1和2）都在生病前饮用过。若变质，3人也饮用过，共3人生病
2. 牛奶2：所有生病者饮用过，但仅2人生病
3. 牛奶3：人物1在生病后才饮用，排除
4. 牛奶4：人物2未饮用却生病，排除

最坏情况下（牛奶1变质）需要治疗3人，因此最少需要3剂药。