题目描述

农民约翰因其农场生产的牛奶质量而闻名于世，他正在为他的$\red{N}$个最好的朋友举办一场牛奶品尝派对$\red{（1≤}$$\red{N≤}$$\red{50). }$不幸的是，在派对上展出的$\red{M}$种牛奶中$\red{（1≤}$$\red{M≤}$$\red{50）}$，其中正好有一个坏了，但农夫约翰不知道是哪一个。任何喝了变质牛奶的人，无论是在派对的剩余时间还是之后，都会生病。

给你一份聚会的记录——谁什么时候喝酒，谁什么时候生病。根据这些信息，你可以推断出哪些牛奶可能是坏的。利用这些知识，帮助农民约翰确定他需要获得的最小剂量的药物，以保证他能够治愈所有在聚 会期间或之后生病的人。

输入格式

输入的第一行包含整数$\red{N}$、$\red{M}$、$\red{D}$和$\red{S}$。

接下来的$\red{D}$线$\red{（1≤}$$\red{D≤}$$\red{1000）}$每个包含三个整数$\red{p，}$$\red{m，}$$\red{t，}$表示人$\red{p}$在时间$\red{t}$喝牛奶$\red{m}$。$\red{p}$的值在$\red{1…}$$\red{N}$ 范围内，$\red{m}$在$\red{1…}$$\red{m}$范围内，$\red{t}$在$\red{1…}$$\red{100}$范围内。一个人可以多次喝同一种牛奶，也可以在同一时间点喝几种类型的牛奶。

接下来的$\red{S}$行$\red{（1≤}$$\red{S≤}$$\red{N）}$ 每个包含两个整数$\red{p，}$$\red{t，}$表示人$\red{p}$在时间$\red{t}$生病。$\red{p}$的值在$\red{1…}$$\red{N}$范围内，$\red{t}$在$\red{1…}$$\red{100}$范围内。每个人最多会生病一次，而他们之所以生病，是因为他们在某个严格意义上的较早时间点喝了变质的牛奶。

输出格式

一个整数，指定 $\red{Farmer John }$需要获得的最小药物剂量，以便他可以保证他将有足够多的剂量来治疗所有生病的人，无论是在聚会期间还是聚会之后。

样例

输入样例

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

提示

有$\red{3}$个人和$\red{4}$种牛奶。第 $\red{1 }$人在第 $\red{3 }$时间生病，第 $\red{2 }$人在第 $\red{8 }$时间生病。第 $\red{3 }$人在聚会上没有生病，尽管我们可能仍需要考虑他在聚会结束后可能会生病的可能性。让我们一一考虑牛奶的种类，看看哪些是可能被污染的；我们知道，如果每个生病的人在生病之前都喝了这种牛奶，那么这种牛奶可能会不好。

牛奶 $\red{1：}$两个病人（$\red{1 }$和 $\red{2）}$在生病前都喝了这种牛奶，所以这可能是坏牛奶。如果是这样，人 $\red{3 }$也喝了，所以总共会导致 $\red{3 }$人生病（聚会后人 $\red{3 }$会生病）。

牛奶$\red{2：}$两个病人在生病前都喝了这种牛奶，所以这也可能是坏牛奶。没有其他人喝过这种牛奶??，所以如果这是劣质牛奶，最坏的情况是总共 $\red{2 }$人可能会生病。

牛奶 $\red{3：}$这不可能是坏牛奶，因为人 $\red{1 }$在生病前没有喝它——人 $\red{1 }$在时间 $\red{4 }$喝了它，在时间 $\red{3 }$生病了。如果牛奶 $\red{3 }$与人 $\red{1 }$生病有牵连，人 $\red{1}$最迟要在时间 $\red{2 }$之前喝完这种牛奶。

牛奶 $\red{4：}$这不可能是坏牛奶，因为人 $\red{2 }$没有喝它，但人 $\red{2 }$生病了。

因此，答案是 $\red{Farmer John }$必须获得 $\red{3 }$剂药物，因为如果牛奶 $\red{1 }$不好，那么总共需要治愈 $\red{3 }$人。